Investigating the Candidate Pair Generation of the VF2 Algorithm

Péter Fehér and László Lengyel


Graph matching, Graph rewriting, Graph transformation, Optimization, Pattern matching, Software algorithms


Recently, model transformation approaches are becoming increasingly popular; therefore their efficiency and usability are key factors and require further investigation. These approaches are regularly used in software engineering, most often as part of the model-driven development methodology. In the case of the graph rewriting-based model transformation approaches, the applied graph matching algorithm greatly determines the efficiency of the transformation approach. The matching algorithm is used to identify sub-graph isomorphism between the transformation rules and the host graph. A widely applied graph matching algorithm is the VF2 algorithm. In this paper we briefly introduce the original VF2 algorithm – specifically, its method – which manages the next possible node pairs. We present a new approach, which increases the efficiency of choosing these node pairs. We also introduce an ordering function, which increases the performance even further. Finally, the effects of these new approaches are presented based on our experimental results.

Important Links:

Go Back