Subgraph Isomorphism Constraint Solving Algorithm Based On Symbolic Techniques

Graph is a very important data structure,composed of nodes and edges,which can be used in real life to represent the relationships between users in social networks or the routes between cities on a map,etc.Subgraph isomorphism problem is a core problem in graph pattern matching,and it is an NP-complete problem.How to improve the efficiency of subgraph isomorphism problem has always been a problem that scholars are committed to solving.Algebraic decision diagram is a data structure used to represent and operate Boolean functions,and its compactness can store more data in the same storage space,and the use of sets as units in the operation process makes the solving process more efficient.In addition,arc consistency technique is mainly used to solve constraint satisfaction problems,by reducing the search space,to achieve the effect of improving solving efficiency.This paper combines algebraic decision diagram to mainly study the subgraph isomorphism constraint solving algorithm based on symbolic technology and arc consistency symbolic filtering algorithm.The main work is as follows:(1)To address the problem of high time and space complexity caused by the construction of candidate set structure in the current subgraph isomorphism solving algorithm,this paper proposes a subgraph isomorphism constraint solving algorithm DDCS based on symbolic technology.The CS structure in the traditional subgraph isomorphism DAF algorithm is encoded and represented by Boolean functions,and further compressed and stored using algebraic decision diagram.Constraints are added to this structure for preprocessing to reduce redundant nodes in the candidate set.At the same time,to reduce the Cartesian product calculation during the search and solving process,the matching order is optimized.Experimental results show that compared with the traditional subgraph isomorphism DAF solving algorithm,the solving efficiency is significantly improved.(2)To address the problem of low efficiency of traditional arc consistency algorithm in solving large-scale complex constraint satisfaction problems,this paper proposes an arc consistency symbolic filtering algorithm DDAC.The constraint satisfaction problem is encoded and represented using Boolean functions,and further compressed and stored using algebraic decision diagrams.In addition,a new variable order is given,which enables the symbol filtering technique to be better integrated with subgraph isomorphism solving algorithms.At the same time,universal quantification operations are introduced in symbol operations to further strengthen the pruning ability of arc consistency techniques.Experimental results show that this filtering algorithm can remove redundant solutions in the value range and improve the efficiency of solving problems.(3)Optimization of the subgraph isomorphism DDCS algorithm.The symbol filtering algorithm DDFilter is introduced in the preprocessing and solving stages of the DDCS algorithm to prune the candidate set,reduce the search space,and improve the efficiency of subgraph isomorphism.Experimental results show that the introduction of the symbol filtering algorithm DDFilter improves the efficiency of the subgraph isomorphism DDCS algorithm.