Study On Subgraph Isomorphism Algorithm Of DAG

Graph is a universal data structure which is widely used to describesemi-structural or structural data, such as WWW, Bioinformatics, XML, SocialNetwork, Software and data project, Chemical Compounds, Protein and GeneIntersection Network, and so on. We rapidly accumulate enormous amount of graphdata with the graph theory in the various fields of successful application. Because ofthe complexity of the graph data and the massive amount of data makes itexceedingly difficult to research and extract available knowledge from the raw data.In recent years, researchers gradually pay close attention to management of theaccumulation of a large graph data (graph database). We retrieve graphs which mustinclude an given graph in a great quantity of graph data. And the given graph namedquery graph. This retrieve graphs include query graph is testing subgraphisomorphism algorithm(Subgraph search algorithm).Testing subgraph isomorphismhas a great important the reality and the actual significance. This algorithm mainlycontains exact subgraph isomorphism test and similar subgraph isomorphism test.Given a graph database and a query graph q. Exact subgraph isomorphism test is {g∈D|g′g, g′is isomorphic to q}; Similar subgraph isomorphism test is {g∈D|g′g, g′is similar isomorphic to q};The typical application of subgraph isomorphism test is extracting knowledgewhich user need from a massive mount of graph database. Subgraph isomorphismtest has its own characteristic and challenges, compared with traditional querytechnology.Such as, several of graph data, data structure is complicated, operation andcontrol demand is sophisticated. Subgraph isomorphism is one of basic inevitableoperation in graph query. And it has been proven that it’s an NP-hard problem.Because of these characteristic and difficulties there are a lot of opportunities forsubgraph isomorphism test. Most of existing subgraph isomorphism test algorithm which is applied to testundirected graph. There are very few subgraph isomorphism test algorithms whichis used to test directed graph. Motivated by this, in this paper we firstly propose anovel and efficient algorithm for testing directed subgraph isomorphism. Weimprove QuickSI algorithm which is applied to test undirected graph and make itcould be used to test directed graph. And in this foundation, it could process testsimilar directed subgraph isomorphism through we make some changes in thisalgorithm. Through a lot of extensive experiments on real and synthetic datademonstrate the efficiency and scalabilit of the proposed algorthim.