A Study Of Algorithms On Reachability Querying For Dynamic Graphs

Reachability between nodes is a basic and important concept in graph theory,it focuses on answering such a question: for any two given nodes u and v on one graph,whether there is at least one path from node u to node v.To obtain the reachability between nodes is called reachability querying.Reachability querying has been an important research topic in computer science and information technology over the past decades.Most of the earliest studies are based on the concept of transitive closure of graph,trying to propose some algorithms to do the reachability querying quickly from a theoretical point of view.With the coming of the information age and the rise of graph-model-based storage mode of data information,reachability querying has received high attention in practical application.And with the increase of the volume of data information,the scale of the graph is also increasing.Therefore,how to obtain the reachability of nodes quickly became one of the most basic problems in data management and application.Over the past several years,many researchers have proposed a variety of efficient reachability querying algorithms,which largely solved the problem of reachability querying on large scale static graphs.However,with the further development of information era,graph-model-based data information is going to be dynamic.Reflecting in graph,that is the insertions and deletions of nodes,and the insertions and deletions of edges between the nodes.The reachability querying algorithm on the static graph can be used to process the reachability querying on the dynamic graph by multiple reuse,but this is not an efficient and feasible way in practice.At this point,some researchers have taken to the study of reachability querying algorithms on the dynamic graphs.In this paper,we made an in-depth research on the reachability querying algorithms for dynamic graphs.Basing on the reachability index and considering the arbitrariness of directed graphs,we proposed a dynamic reachability querying algorithm which is applicable to arbitrary directed graphs and able to deal with the insertions and deletions of edges.The time complexity of the algorithm is analyzed,and the correctness of the algorithm is guaranteed by the necessary proof.Under this condition,we took the experiment to compare with the existing dynamic reachability querying algorithm which has the same processing capability.The experimental result on both simulation data set and real data set showed that the dynamic reachability querying algorithm presented in this paper has a remarkable general advantage.