Multi-Constrained S-t Paths Enumeration On Temporal Graph

Graph is a ubiquitous structure representing entities and their relationships.Studying the relationship between two vertices is a fundamental problem in graph analysis,and paths are widely used to measure the relationship between two vertices.s-t paths enumeration has received more and more attention in recent years.Simply enumerating all paths between two vertices cannot meet the requirements in some cases.Considering the universality of temporal information in real life,in this paper,we study the problem of multi-constrained s-t paths enumeration on temporal graph.Firstly,a two-stage algorithm based on converted subgraph is proposed.In the first stage,the Vertex Pruning Algorithm(VPA)is proposed,which uses Dijkstra algorithm to traverse the temporal graph bidirectionally to calculate the vertex and time information on the path.An algorithm for creating converted subgraphs(CCSGA)is also proposed,which uses graph transformation technology and the results of VPA algorithm to create a small converted subgraph to narrow the search range.In the second stage,the depth-first search algorithm is used to find the paths on the converted subgraph,and pruning strategies are proposed to prune the search branch that cannot be used to find new paths.Secondly,a two-stage algorithm based on temporal subgraph is proposed.In the first stage,three algorithms for creating temporal subgraph are proposed.The first creates temporal subgraph based on temporal graph.Use the results of VPA algorithm and edge pruning strategies to calculate the temporal subgraph.The second creates temporal subgraph based on converted graph.Use the breadth-first search algorithm to traverse the converted graph bidirectionally.The temporal subgraph is obtained after pruning the converted graph with the flag of vertex.The third creates temporal subgraph based on edge stream.Optimize the sequence of edge streams,traverse the sequence of edge streams bidirectionally,and use flags to prune edges.In the second stage,the depth-first search algorithm is used to find the paths on the temporal subgraph,and the pruning strategies are used to reduce the search space.Finally,experiments on real datasets demonstrate the efficiency of the proposed algorithms.