Coincidencia de patrones en gráficos

Question

Estoy tratando de encontrar herramientas/algoritmo para buscar secciones que corresponda al patrón especificado en gráfico orientado, por ejemplo:

A-> b-> c o o a <-> b-> c

Por favor, sugiéreme la dirección de mis búsquedas.

Me refiero a la coincidencia de patrones. Necesito encontrar todo el grupo de nodos y bordes, ese patrón especificado de coincidencia

Answer 1

¿No es este el Problema de isomorfismo de subgraph? En caso afirmativo, la página de Wikipedia contiene una sección sobre algoritmos.

Answer 2

La coincidencia de patrones de gráficos es la funcionalidad en el núcleo de Herramientas de reescritura de gráficos, lo ofrecen preimplementado.

En EG Grgen, escribe su patrón de ejemplo como A: A -> B: B -> C: C, la herramienta genera un combate de patrón para él, uno que se adapta a las características del gráfico host (optimizado por Teniendo en cuenta las estadísticas sobre el gráfico).

Answer 3

Con respecto a las posibles bibliotecas, puede encontrar una respuesta aquí Biblioteca de gráficos de Python.

En cuanto a la coincidencia de patrones, si conoce el patrón que está buscando, solo necesita atravesar el gráfico y comparar las rutas o puede usar una función para recuperar una ruta entre los nodos y verificar si el patrón existe.