Implementation of a Subgraph Matching Algorithm - Graphmatcher
Emre Ünlü · Aaltodoc (Aalto University) · 2017
As graph databases and using graph as a data structure attract more and more interest of the industry, inevitably research towards to graphs is also accelerated by this interest. Significant amount of effort has been dedicated to graph theory related research by IT industry giants such as Google and IBM with Cayley or Facebook with GraphQL. In the domain of graph theory, Subgraph Matching is one of the basic graph problems which has always room for an improvement. Therefore, numerous methods and algorithms have been developed to produce better results for different class of input graphs, such as Ullmann's Algorithm, VF2, GraphQL, TurboISO and DualISO. In this work, I have attempted to solve a subgraph matching problem encountered in a task scheduling system for software development processes. In the same vein, problem that I was attempting to solve also touched to a scheduling problem known as Job Shop Problem. To solve both problems efficiently at one time, I have developed our subgraph matching method, Graphmatcher. It is essentially a fork of DualISO algorithm with additional functionality towards efficient solution of scheduling problems I have encountered. In the practical part of this thesis, I have given detailed information about design and implementation of Graphmatcher and task scheduler application. Also I have explained how does Graphmatcher add value into task scheduling application and what kind of effect does it make under different conditions. To prove efficiency of our method, I have written tests which use various combinations of parameters and made observations from production environment. Based on results, I claim that our method of Graphmatcher is able to solve similar problems with ease and add value into software development processes by utilizing more resources at once.