A multilayer approach to subgraph matching in HP-graphs

Визуальное моделирование на данный момент широко распространено, однако существующие платформы, предназначенные для моделирования, не могут удовлетворить все требования пользователей. Визуальные языки, как правило, основаны на графовых моделях, однако графовые формализмы, используемые для представления моделей, обладают существенными ограничениями. Для решения проблемы недостаточной выразительности существующих графовых моделей ранее была представлена новая графовая модель ($HP$-граф), основным элементом которой является множество полюсов, подмножества которых объединены в вершины и гиперребра. Многие операции над визуальными моделями, включая трансформацию моделей, сталкиваются с проблемой поиска изоморфного подграфа, что оказывает значительное влияние на скорость их выполнения. Многослойная структура $HP$-графа позволяет снизить временную сложность алгоритмов поиска. Количество операций может быть снижено благодаря тому, что поиск изначально осуществляется на слое вершин и гиперребер, и только в случае нахождения подграфа с желаемыми характеристиками алгоритм переходит на более детальный уровень, где сравниваются наборы соответствующих полюсов и обыкновенных связей отобранных подграфов. Представлено описание идеи многослойного подхода. Предложен алгоритм поиска с возвратом, основанный на этом подходе. Алгоритмы Ульмана и VF2 адаптированы к данному подходу, выполнена оценка их временной сложности. Предложенный подход постепенно сокращает область поиска алгоритмов и помогает уменьшить их общую сложность. В статье доказывается, что существующие алгоритмы сопоставления подграфов, за исключением тех, которые изменяют шаблон графа, могут быть успешно адаптированы к предлагаемому подходу.