Многослойный подход к поиску изоморфных подграфов в HP-графах

Proceedings of the Institute for System Programming of the RAS. 2021. Vol. 33. No. 4. P. 163–176.

N.M. Suvorov, L.N. Lyadova

Visual modeling is widely used nowadays, but the existing modeling platforms cannot meet all the user requirements. Visual languages are usually based on graph models, but the graph types used have significant restrictions. A new graph model, called HP-graph, whose main element is a set of poles, the subsets of which are combined into vertices and edges, has been previously presented to solve the problem of insufficient expressiveness of the existing graph models. Transformations and many other operations on visual models face a problem of subgraph matching, which slows down their execution. A multilayer approach to subgraph matching can be a solution for this problem if a modeling system is based on the HP-graph. In this case, the search is started on the higher level of the graph model, where vertices and hyperedges are compared without revealing their structures, and only when a candidate is found, it moves to the level of poles, where the comparison of the decomposed structures is performed. The description of the idea of the multilayer approach is given. A backtracking algorithm based on this approach is presented. The Ullmann algorithm and VF2 are adapted to this approach and are analyzed for complexity. The proposed approach incrementally decreases the search field of the backtracking algorithm and helps to decrease its overall complexity. The paper proves that the existing subgraph matching algorithms except ones that modify a graph pattern can be successfully adapted to the proposed approach.

Keywords: изоморфизм, графовая модель, isomorphism, алгоритмы на графах, визуальная модель, subgraph matching, DSM platform, visual model, graph model, HP-graph, algorithms on graphs, HP-граф, DSM платформа, поиск изоморфного подграфа