python - Coincidencia de patrones en gráficos

graph pattern-matching

Question

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

A-> B-> C or o A <-> B-> C

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

Me refiero a la coincidencia de patrones. Necesito encontrar todos los grupos de nodos y bordes, que coincidan con el patrón especificado

Answer 1

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

Answer 2

La coincidencia de patrones gráficos es la funcionalidad en el núcleo de las herramientas de reescritura de gráficos , que ofrecen pre-implementada.

En, por ejemplo, GrGen se escribe su patrón de ejemplo como: A -> b: B -> c: C, la herramienta genera un patrón de coincidencia para ello, uno que se adapta a las características del gráfico de host (optimizado por tomando 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 recorrer el gráfico y comparar las rutas o puede usar una función para recuperar una ruta entre nodos y verificar si el patrón existe.