Сопоставление с образцом в графиках

Question

Я пытаюсь найти инструмент / алгоритм для поиска разделов, который соответствует указанному шаблону в ориентированном графе, например:

A-> B-> C или или A <-> B-> C

Пожалуйста, предложите мне направление моих поисков.

Я имею в виду сопоставление с образцом.Мне нужно найти всю группу узлов и ребер, которые соответствуют указанному шаблону

Answer 1

Разве это не проблема изоморфизма подграфа ? Если да, на странице Википедии есть раздел об алгоритмах.

Answer 2

Сопоставление с графическим шаблоном - это функциональность, лежащая в основе инструментов переписывания графиков , они предлагают его предварительно реализованным.

Например, Если вы запишите свой пример шаблона как a: A -> b: B -> c: C, инструмент генерирует для него шаблон сопоставления, который адаптируется к характеристикам графа хоста (оптимизируется путем сбора статистики о графике в счет).

Answer 3

Относительно возможных библиотек вы можете найти ответ здесь Python Graph Library .

Что касается сопоставления с шаблоном, если вы знаете шаблон, который ищете, вам просто нужно пройти по графику и сравнить пути, или вы можете использовать функцию, чтобы получить путь между узлами и проверить, существует ли шаблон.