| Popis: |
For a given pair of pattern and data graphs, the subgraph isomorphism finding problem locates all instances of the pattern graph into the data graph. For a given subgraph isomorphic image of the pattern graph in a data graph, the set of all ordered pairs of the pattern graph’s vertices and their respective images data graph is called an embedding. Many solvers, such as $\mathrm {Turbo_{ISO}}$ , Glasgow, and VF3 exist in the literature for subgraph isomorphism finding problem. Though each solver aims to minimize computing costs in its own way, computational efficiency is still a central issue for the subgraph isomorphism finding problem. In this paper, we present the development of an efficient solver, SubGlw, for subgraph isomorphism finding which first decomposes data graph into small-size candidate subgraphs using a ranking function and then searches the embeddings of the pattern graph in each of them separately. The ranking function is designed in such a way that it minimizes both number and size of the candidate subgraphs. The performance of SubGlw is empirically evaluated and compared with two state-of-the-art subgraph isomorphism solvers – SubISO and Glasgow over three benchmark datasets – Yeast, Human, and Hprd. The experimental findings reveal that SubGlw performs significantly better in terms of both embedding count and execution time. We have also presented an analysis for identifying saddle point, which is a timeout at which our solver achieves maximum embeddings in least execution time. This analysis provides a better understanding for parameter settings. The source codes of SubGlw can be downloaded from https://github.com/ZubairAliIgraph/SubGlw-master. |
