Malti-Constrained Temporal Path Query In Temporal Graphs

In recent years,with the arrival of the era of big data and the rise of online social net-works,the algorithm research on the graph is becoming more and more popular,because both the social network and the road network can be regarded as a graph.So far,various excellent algorithms have been applied to practical applications and bring great convenience to peopled daily life.However,existing algorithms mostly consider static graphs and a sin-gle attribute,while ignoring the temporality and multiple attributes in real life.For example,in the road network,people need to consider whether there are shifts between two points at different times.when travelling,in addition to considering the time factor,people often consider the degree of congestion of roads,fuel consumption and other factors.Based on the above situation,this paper studies the multi-constrained path query prob-lem based on temporal graph.We do some expansion and innovation based on the traditional path query algorithm.We embed the time series information and multi-attribute information into the modeling and processing of the graph,which is more real and provides users with more accurate and detailed results.This paper is dedicated to finding the target path that satisfies the user,s multiple attribute constraints on the temporal graph.The target path here includes the fastest arrival path and the path with the shortest running time.To solve the above problems effectively and efficiently,we propose two algorithms based on Skyline path and Two-Pass based respectively.They fully consider the timing fea-tures and multiple attributes on the graph,and continuously pruning and optimizing in the process of query,which greatly reduces the search space.The algorithm based on Skyline path first solves the problem of timing by transforming the temporal graph into the stat-ic graph,then it solves the problem of multiple attributes by calculating the Skyline path,Finally,the target path is selected according to the results of the previous two steps.The Two-Pass algorithm is based on forward and backward search.The reverse direction quickly determines whether the path satisfies the constraint according to the designed target equation and then solves the target path in the forward direction.Our comparative experiments on re-al datasets demonstrate the efficiency and effectiveness of these two algorithms.Finally,we implement a multi-constrained temporal path query system.