Get best of the week

Verificación del isomorfismo de dos gráficos y búsqueda de subgráficos isomórficos: un enfoque basado en el análisis de rutas NB

Hola a todos.

Existe tal tarea: verificar si dos gráficos son isomórficos entre sí. Es decir, simplemente, para averiguar si ambos gráficos son "el mismo" gráfico, pero con diferentes números de vértices y, si los gráficos se especifican gráficamente, con diferentes ubicaciones espaciales. La solución a este problema no es tan obvia como podría parecer a primera vista: incluso para gráficos pequeños, un vistazo a su representación gráfica no siempre dará una respuesta inequívoca. Vea, por ejemplo, un dibujo en el mismo Wiki: en.wikipedia.org/wiki/Graph_isomorphism#Example .

¿Bueno obviamente?

Pero hay una tarea más difícil: buscar en un gráfico "grande" todas las subgrafías isomorfas a algún otro gráfico "más pequeño". Este es un aún más "bosque oscuro". Eso, por supuesto, no es del todo oscuro, pero la tarea, como puede ver, no es la más fácil.

¿Entonces que tenemos?

1. ¿Por qué es todo esto necesario?


Y aunque el problema de los (sub) gráficos isomórficos, como ya hemos mencionado, es complicado, es bastante necesario y útil. ¿Para qué? Y luego, por ejemplo, buscar en la base de datos compuestos químicos similares a una molécula dada por su fórmula estructural. Después de todo, se puede imaginar como un gráfico, ¿verdad? La quimioinformática hace esto: existe tal ciencia. Pero también hay tareas de comparación con la muestra, varias tareas bioinformáticas y muchas otras cosas interesantes.

2. ¿Cómo resolver este problema?


El enfoque clásico para resolver este problema fue establecido por J. Ullman en 1976 [3], más tarde mejoró sustancialmente su algoritmo [4]. Además, este enfoque se desarrolló aún más en los trabajos de muchos otros autores, por ejemplo, Cordella y coautores [2] (algoritmo VF2), Bonnitsi y coautores [1] (algoritmo RI), etc.

En resumen, la esencia de este enfoque es "inteligente enumerando ”las posibles correspondencias de los vértices del gráfico de muestra B y el gráfico A en el que se está buscando. Esta búsqueda hace que sea "inteligente" ingresar varias condiciones y restricciones que le permiten cortar las opciones inadecuadas lo antes posible. Además, para estos fines, se pueden llevar a cabo diversos procesamientos preliminares de los datos fuente.

No nos ocuparemos de volver a contar estos trabajos aquí, pero invitaremos al lector a conocerlos de forma independiente. Sin embargo, "un espectáculo es mejor que un pedido", y debe tenerse en cuenta que hay buenos ejemplos gráficos y explicaciones de estos algoritmos en la Web. Vea, por ejemplo, lo siguiente:
coderoad.ru/17480142/Is-or-simple-example-for-explanation-algorithm-Ulman - una explicación muy buena y clara con un ejemplo,
issue.life/questions/8176298 - pasos del algoritmo VF2 con un ejemplo .

Sin embargo, surge la pregunta: ¿existen otras formas y enfoques posibles para resolver este problema, aunque en algunos casos especiales? Y me gustaría presentarle una de las posibles respuestas a esta pregunta.

2. Isomorfismo de gráficos y rutas NB


Acordemos de inmediato: en NB -paths (y no del inglés, sino simplemente porque es muy corto) llamaremos rutas no ramificadas máximas, es decir. Trayectos no ramificados máximamente largos de algún gráfico.

Entonces, si tenemos dos gráficos que son isomórficos entre sí , entonces, para cualquier representación del primer gráfico como una secuencia de rutas no ramificadas máximamente extendidas (es decir, nuestras rutas NB), siempre existe la misma representación de la segunda gráfica correspondiente, y al mismo tiempo:

  • para gráficos dirigidos, las rutas correspondientes entre sí se alinearán,
  • los grados de vértices correspondientes entre sí para gráficos no dirigidos (y para gráficos orientados, el número de bordes entrantes y salientes, respectivamente) será igual a
  • al "combinar" tales representaciones como resultado, tendremos una correspondencia de los vértices de los gráficos primero y segundo.

Un ejemplo . Gráfico A = {1-> 2, 1-> 6, 4-> 5, 5-> 1, 3-> 3}. Gráfico B = {3-> 4, 3-> 5, 1-> 2, 2-> 3, 6-> 6}
Rutas A (rutas máximas no ramificadas de A ): 1-> 2, 1-> 6, 4-> 5-> 1, 3-> 3
Rutas B (rutas máximas no ramificadas de B ): 3-> 4, 3-> 5, 1-> 2-> 3, 6-> 6 Coincidencia de vértices
: 1 ( A): 3 (B), 2 (A): 4 (B), 6 (A): 5 (B), 4 (A): 1 (B), 5 (A): 2 (B), 3 ( A): 6 (B).

Por lo tanto, el problema de verificar el isomorfismo de dos gráficos se puede resolver encontrando dichos caminos correspondientes entre sí y luego verificando la igualdad de las matrices de adyacencia construidas en función de su conservación del orden de los vértices en las secuencias de ruta obtenidas (cada vértice se agrega a la secuencia una vez, primera "mención"). En nuestro ejemplo, los siguientes órdenes de vértices se utilizarán para construir matrices de adyacencia:

A : 1, 2, 6, 4, 5, 3
B : 3, 4, 5, 1, 2, 6

Matriz de adyacencia para A para un orden dado de vértices:

imagen

matriz de adyacencia para B para un orden dado de vértices: las

imagen

matrices son iguales; por lo tanto, las gráficas A y B son isomorfas.

Además, este enfoque (1) es aplicable tanto para gráficos orientados como no orientados, (2) es aplicable para gráficos que contienen más de un componente conectado / fuertemente conectado, (3) es aplicable para gráficos que contienen múltiples aristas y bucles (múltiples) (4) no tiene en cuenta los vértices para los que no hay bordes incidentes.

3. Bueno, verificó el isomorfismo de los gráficos. ¿Pero qué hay de la búsqueda de subgrafías?


Y aquí, francamente, todo es mucho más complicado. Aquí tendremos la siguiente restricción: en función de la esencia misma del método, no puede encontrar ninguno, sino solo subgrafos "inscritos" . Y llamaremos al subgrafo "inscrito" del gráfico A un subgrafo que se puede "pegar" a otras partes del gráfico A solo debido a bordes incidentes solo en los vértices de límite de sus (subgrafos) caminos no ramificados de longitud máxima (además, el gráfico A puede contener otros componentes conectados) No se preocupe, a continuación será un ejemplo, y todo será más claro.

Además, al resolver este problema, además de buscar la correspondencia de NB rutas de gráficos A y B de longitud (como fue el caso con la prueba de isomorfismo anterior), también es necesario buscar por separado las siguientes correspondencias posibles entre ellas:

  • Correspondencia de rutas NB: cadenas simples del gráfico B a rutas NB: cadenas simples / ciclos simples del gráfico A. Además, inicialmente tales rutas en el gráfico A pueden ser más largas; en este caso, se toman sus segmentos que son iguales en longitud a la ruta deseada desde B.
  • Correspondencia de las rutas NB- “final” del gráfico B a cualquier ruta NB de la gráfica A (en este caso, las rutas desde la gráfica A también pueden ser más largas; en este caso, se toman sus segmentos que son iguales en longitud a la ruta deseada desde la gráfica B).

Veamos un ejemplo:

imagen

al buscar un subgrafo isomorfo "inscrito" del gráfico B en la columna A (ver figura anterior), se encontrarán las siguientes correspondencias:

  • ruta interna 2-> 3-> 4 de la columna B: ruta interna 2-> 3-> 4 de la columna A,
  • rutas finales 1-> 2 y 10-> 2 del gráfico B: ruta final 0-> 2 del gráfico A y un fragmento de la ruta final 7-> 1-> 2 del gráfico A, a saber 1-> 2,
  • 7->8 B: 9->10->11 A, 9->10 10->11, 12->13->14->12 A, 12->13, 13->14, 14->12.

Por lo tanto, como las subgrafías "inscritas" del gráfico A que son isomorfas al gráfico B, se pueden encontrar las siguientes 5 opciones:

A1 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 9-> 10}
A2 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 10-> 11}
A3 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 12-> 13}
A4 = {0-> 2, 1-> 2, 2 -> 3, 3-> 4, 4-> 5, 4-> 6, 13-> 14}
A5 = {0-> 2, 1-> 2, 2-> 3, 3-> 4, 4-> 5, 4-> 6, 14-> 12}

Sin embargo, si agregamos un borde adicional 3-> 8 al gráfico A, obtenemos el gráfico A '(abajo en la misma figura). Y en A 'ya no habrá subgrafos "inscritos" isomorfos al gráfico B. De hecho: el borde 3-> 8 "divide" el camino 2-> 3-> 4 del gráfico A en dos y, por lo tanto, caminos candidatos para el camino interno 2 ->3-> 4 columnas B no se encontrarán.

4. Ahora el algoritmo mismo


Ahora podemos pasar a un examen más detallado del algoritmo de búsqueda para los subgrafos "inscritos" en la columna A que son isomorfos a alguna columna B.

Por lo tanto, el algoritmo constará de 4 etapas:

  • Preprocesamiento
  • Pareo
  • Adelgazamiento,
  • Conclusión

Etapa I. Preprocesamiento


En esta etapa, encontramos todas las rutas NB para cada uno de los gráficos, así como también evaluamos los factores que limitan el espacio de elección durante la enumeración. Aquellos. hacemos lo siguiente:

  1. Encontramos todas las rutas NB en la columna A y las colocamos en una matriz dinámica (en C ++ - en un vector).
  2. Encontramos todas las rutas NB en la columna B y las colocamos en una matriz dinámica (vector).
  3. A B. II-IV , 1. A- B B: - , B.
  4. A B ( ).
  5. A B: DA DB .
  6. – B00 – B , , .

Entonces, tenemos NB-caminos en ambos gráficos y parámetros de límite de p.p. 3-5.

Etapa II Cartografía


En esta etapa, seleccionaremos rutas NB candidatas (en lo sucesivo, simplemente denominadas "rutas candidatas") de la columna A para cada una de las rutas NB de la columna B. Marcado de cada ruta candidata desde las Rutas A para cada i-ésima Rutas B [i ] se escribirá en una matriz dinámica bidimensional (en C ++ - en un vector de vectores) NPaths - respectivamente en el i-ésimo vector (i-ésima línea) - en la forma de un triple ordenado de números: el número de la ruta correspondiente en PathsA - el número de la posición inicial en él - la longitud de la ruta .

Por ejemplo, las rutas B [2] = {1, 0, 3, 3, 1, 3} significa que las rutas B [2] están asociadas con 2 rutas candidatas desde A: desde las rutas A [1] - los primeros 3 elementos de ruta que comienzan desde cero ( initial) y from PathsA [3]: también 3 elementos que comienzan desde el primero (junto al inicial).

Al mismo tiempo, buscaremos (seleccionaremos) rutas candidatas en 4 direcciones:

  1. Busque las rutas candidatas para todas las rutas internas NB del gráfico B desde las rutas B, es decir aquellos cuyos dos vértices límite están conectados en el gráfico B con al menos otros 2 vértices (independientemente de la dirección de dicha conexión), y de esta manera no es un ciclo simple (orientado - para gráficos orientados).
  2. Busque rutas candidatas para rutas NB finales de PathsB.
  3. Busque rutas candidatas para rutas NB: bucles simples de PathsB.
  4. Busque rutas candidatas para rutas NB: rutas simples de PathsB.

Al seleccionar rutas candidatas para cada i-ésima ruta de PathsB, se comparan (aquí es donde algunos de los parámetros limitadores previamente calculados son útiles):

  • su longitud y la longitud de la ruta candidata (debe ser igual para los casos 1 y 3, y para los casos 2 y 4 la ruta candidata de las rutas A también puede ser más larga),
  • los grados de sus vértices de límite y los vértices correspondientes de la ruta candidata (para los vértices de la ruta candidata, estos valores deben ser al menos la ruta de las rutas B).

Si, de acuerdo con los resultados de la etapa II, no se encontró una sola ruta candidata de las Rutas A para ninguna de las rutas en las Rutas B, entonces se considera que A no contiene subgrafos "inscritos" isomorfos a la columna B.

Adelgazamiento


Ahora intentemos "exprimir" el gráfico A. Dejamos en él solo aquellos bordes que entraron en los caminos candidatos que encontramos. Si, al mismo tiempo, el gráfico A ha perdido al menos un borde en comparación con su estado inicial, entonces volvemos a la etapa I "Preprocesamiento": los grados de los vértices del gráfico A y, en consecuencia, la lista de rutas candidatas se puede reducir y, en consecuencia, el espacio de búsqueda se puede reducir.

Etapa III Adelgazando la lista de caminos candidatos


El propósito de este paso es eliminar aún más la mayor cantidad posible de candidatos inapropiados. Para hacer esto, llevamos a cabo los siguientes pasos.

  1. La exclusión de rutas candidatas obviamente inapropiadas en función de las distancias mínimas entre los vértices en la columna B. La ruta candidata para cada ruta B [i] para la que al menos una ruta B [j] no se encontró ninguna ruta candidata para el más corto la distancia entre sus vértices de límite en el gráfico A era menor o igual a la distancia más corta entre los vértices de límite correspondientes de los caminos PathsB [i] y PathsB [j] desde el gráfico B.
  2. Una excepción para todos los ciclos de PathsB a rutas candidatas no cíclicas asociadas y viceversa.
  3. La excepción de las rutas candidatas similares a la Sección 1, pero no por el criterio de la distancia más corta entre vértices límite, sino por sus (vértices límite) a la igualdad o desigualdad mutua.

Por ejemplo, si:

  • el elemento inicial de PathsB [i] no es igual al elemento inicial de PathsB [j], y
  • el elemento final de PathsB [i] no es igual al elemento final de PathsB [j], y
  • el elemento inicial de PathsB [i] es igual al elemento final de PathsB [j], y
  • el elemento inicial de PathsB [j] no es igual al elemento final de PathsB [i],

la ruta candidata a lo largo de la ruta B [i] para la cual al menos una ruta B [j] no tiene rutas candidatas que cumplan la condición anterior con respecto a la igualdad / desigualdad de sus (rutas candidatas) iniciales y finales, respectivamente, está sujeta a exclusión picos

Es decir, en términos generales, descartamos aquellas rutas candidatas que obviamente no se incluirán en los subgrafos deseados, en función de la distancia a todas las demás rutas candidatas (estas rutas están terriblemente lejos de todas las demás), en función de su ciclicidad / no ciclicidad, y también se basa en la debida igualdad / desigualdad de sus vértices de límite con vértices de límite de otras rutas candidatas.

Si, de acuerdo con los resultados de la etapa III, se eliminó al menos 1 ruta candidata de las Rutas A, entonces, nuevamente, la columna A se actualiza, solo aquellos bordes que están incluidos en las rutas candidatas restantes permanecen en ella. Y, nuevamente, si al mismo tiempo, el gráfico A “perdió peso” por al menos un borde, volvemos nuevamente a la etapa I “Preprocesamiento”: los grados de los vértices del gráfico A y, en consecuencia, la lista de rutas candidatas se puede reducir y, en consecuencia, se puede reducir buscar espacio

Etapa IV Conclusión


Cada combinación posible de todas las rutas candidatas restantes define un subgráfico de la columna A. Para cada una de estas subgrafías, se construye una matriz de adyacencia teniendo en cuenta el orden de las rutas candidatas de la misma manera que se construyó la matriz de adyacencia B00 para el gráfico B, y luego se comparan estas matrices de adyacencia.

Si son iguales, se comparan las multiplicidades de los bordes (consulte la sección 3 del preprocesamiento de la etapa I). Si se cumplen todas estas condiciones, el subgrafo encontrado se considera isomorfo al gráfico B y se agrega al conjunto de resultados encontrados.

Durante la “Conclusión” de la etapa IV, se pueden usar varias verificaciones adicionales para acelerar la identificación y el rechazo de un subgráfico inapropiado.

5. Cómo se confunde todo ... Considere un ejemplo del algoritmo


No sé tú, pero sería incomprensible para mí sin un ejemplo. Veamos un ejemplo.

En la Fig. los gráficos a continuación son A = {1-> 2, 2-> 5, 5-> 15, 16-> 15, 5-> 5, 5-> 5, 5-> 4, 5-> 6, 7-> 6 , 6-> 8, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 0-> 12, 4-> 13, 13-> 14, 14-> 4 } y B = {1-> 1, 4-> 5, 5-> 1, 1-> 3, 3-> 3, 3-> 2, 2-> 7, 2-> 8, 9-> 10, 10-> 9, 1-> 6, 6-> 11, 11-> 12, 12-> 6}. Nuestra tarea es encontrar en el gráfico A todos los subgrafos "inscritos" isomorfos al gráfico B. El resultado también se muestra en la figura: los vértices y bordes encontrados del gráfico A están resaltados por una línea gruesa, y los números de los vértices correspondientes del gráfico B se indican entre paréntesis (si hay varias opciones, se indican mediante fracción).

imagen

Al resolver el problema de búsqueda en la columna A de los subgrafos "inscritos" isomorfos a la columna B,Tenemos los siguientes resultados del algoritmo.

Etapa I: Todas las acciones y cálculos se realizaron de acuerdo con p.p. 1-5 de este paso, las siguientes son las rutas A y B resultantes.

Rutas A:

1-> 2-> 5
4-> 13-> 14 4
5-> 4
5-> 5
5-> 6
5-> 15
6-> 6
6-> 8
6-> 9
7-> 6
9 -> 10
9-> 11
16-> 15
0-> 12-> 0

Trayectos B:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4- > 5-> 1
6-> 11-> 12-> 6
9-> 10-> 9

Etapas II-III. La comparación mostró que para cada ruta de PathsA hay al menos una ruta candidata de PathsB, y PathsA fue acortada por los resultados del adelgazamiento preliminar. En la etapa de adelgazamiento principal (III), no se produjo una mayor reducción de PathsA. Como resultado, PathsA y PathsB tomaron la forma:

PathsA:

1-> 2-> 5
4-> 13-> 14-> 4
5-> 4
5-> 5
5-> 6
6-> 6
6-> 9
9-> 10
9-> 11
0-> 12-> 0

Trayectos B:

1-> 1
1-> 3
1-> 6
2-> 7
2-> 8
3-> 2
3-> 3
4-> 5-> 1
6 -> 11-> 12-> 6
9-> 10->9

La comparación final de NPaths es:
NPaths:

i = 0: 3 0 2
i = 1: 4 0 2
i = 2: 2 0 2
i = 3: 7 0 2 8 0 2
i = 4: 7 0 2 8 0 2
i = 5: 6 0 2
i = 6: 5 0 2
i = 7: 0 0 3
i = 8: 1 0 4
i = 9: 9 0 3

Aquí es el momento de recordar que cada triplete ordenado de números en NPaths [i] define la ruta candidata correspondiente a las rutas B [i] desde A en el formato: el número de la ruta correspondiente desde las Rutas A - la posición inicial del segmento desde esta ruta - la longitud del segmento. Por lo tanto, es fácil verificar que las rutas B [0] = {1-> 1} (i = 0: 3 0 2) corresponden a la única ruta desde A, es decir, el segmento desde las rutas A [3], comenzando desde el principio y tener una longitud de 2.

Etapa IV. Como resultado, el único subgrafo A1 se encontró en la columna A que es isomorfo a la columna B. A1 = {0-> 12, 1-> 2, 2-> 5, 4-> 13, 5-> 4, 5-> 5, 5- > 6, 6-> 6, 6-> 9, 9-> 10, 9-> 11, 12-> 0, 13-> 14, 14-> 4}.

5. ¿Qué sigue?


Y luego, en principio, eso es todo. Aunque no del todo: el autor debe admitir que el algoritmo aún se puede finalizar y finalizar. ¿Qué hay para agregar?

  1. Cuando se introducen características adicionales de los vértices de las columnas A y B (por ejemplo, cuando los compuestos están dados por las gráficas de compuestos químicos, se puede asociar un código numérico correspondiente a un solo átomo (isótopo) con cada vértice), el proceso de búsqueda se puede acelerar debido a la mayor precisión de las comparaciones según la Etapa II: adicional La condición para seleccionar las rutas candidatas será la correspondencia de las etiquetas de vértice.
  2. . , «», «» - B.
  3. , , , «» :
    (1) «» , ,
    (2) .
    «» « - », , , .
  4. , - , .


General sobre los problemas:
1. Bonnici, V., Giugno, R., Pulvirenti, A. et al. Un algoritmo de isomorfismo subgráfico y su aplicación a datos bioquímicos. BMC Bioinformatics 14, S13 (2013). doi.org/10.1186/1471-2105-14-S7-S13 .
2. Cordella L, Foggia P, Sansone C, Vento M: A (Sub) Gráfico Algoritmo de isomorfismo para emparejar gráficos grandes. Transacciones IEEE sobre análisis de patrones e inteligencia artificial. 2004, 26 (10): 1367-1372. 10.1109 / TPAMI.2004.75.
3. Ullmann Julian R.: Un algoritmo para el subgrafo isomorfismo. Revista de la Asociación de Maquinaria Informática. 1976, 23: 31-42. 10.1145 / 321921.321925.
4. Ullmann Julian R.: Algoritmos de vector de bits para satisfacción de restricción binaria e isomorfismo de subgrafo. J Exp Algoritmos. 2011, 15 (1.6): 1.1-1.6. 1,64

La preimpresión del autor escrita en un idioma más oficial sobre esto es el más "algoritmo basado en NB-Paths", que también contiene información sobre un intento de implementarlo en C ++:
5. Chernoukhov SA 2020. Preprints.RU. Comprobación del isomorfismo de dos gráficos y búsqueda de subgrafos "inscritos" isomorfos: un enfoque basado en el análisis de caminos de ramificaciones no ramificadas maximizadas para resolver el problema del isomorfismo (sub) gráfico. DOI: dx.doi.org/10.24108/preprints-3111977 Fuentes

útiles de Internet sobre el tema:
6. coderoad.ru/17480142/Is-lii- simple-example-for-explicación-algoritmo-Ulman
7. issue.life/questions / 8176298 .

More articles:


All Articles