This repository contains the generic implementation of the A*(star) algorithm for dynamic graphs. Full code in repository: link
A* is one of the widely used path planning and shortest path approximation algorithms. It is applied in a diverse set of problems from path-finding in video games and robotics to codon optimization in genetics. In this work, we focus on A* for graphs that are subjected to update operation, where an update operation refers to the insertion or deletion of an edge. Instead of performing A* again from start each time graph is subject to update, our algorithm process the sub-graphs which are affected by the update. For temporal graph available at SNAP for 100 updates we got 25x-40x of performance improvement over repeated A* search. More details
- Supports both directed and undirected positively weighted graphs
- Supports all types of heuristics function
- Supports insertions/deletions of edges onto the graph
- Uses Diff CSR to store dynamic graphs
- improved performance from repeated A* search
To use this library ensure you meet the following requirements:
Linux
-
gcc and g++ with std c++11
-
CUDA >= 10.0
This library is self-contained in the header files at the include directory of this repository with all required classes and functions defined.
-
You can copy the headers of this library to your projects include directory :
cp -r DA_STAR/include/ <your-project>/include/
-
Or You can copy the headers of this library to your root/CUDA include folder
sudo cp -r DA_STAR/include/ /usr/include/cp -r DA_STAR/include/ <CUDA_PATH>/include/
#include "include/dynamic_graph.cuh"
#include "include/d_a_star.cuh"
#include "include/utils.cuh"
int main(){
std::string input_graph = "graph.txt";
std::string input_updates = "updates.txt";
//reuires weight type
GPU_Dynamic_Graph<unsigned int> graph;
graph.read(input_graph);
int start_node = 0; //start node
int end_node = 7; //end node
int num_pq = 10; //number of parallel priority queue
//requires weight type and heuristics/Cost type
GPU_D_A_Star<unsigned int, int> algo(&graph,start_node,end_node,num_pq);
graph.set_update_file(input_update);
while(graph.update()){
std::vector<int> path = algo.get_path();
print_path(path);
}
return 0;
}