lkoshale/da_star

A* ( Star) algorithm for dynamic graphs on GPU

DA_STAR

This repository contains the generic implementation of the A*(star) algorithm for dynamic graphs. Full code in repository: link

About

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

Features

• 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

System Requirements

To use this library ensure you meet the following requirements:

Linux

• gcc and g++ with std c++11

• CUDA >= 10.0

How to Build

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/

Examples

#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;
}

Dynamic Graphs

Credits

da_star's Issues

Bugfix & Memory leak fix

There is a bug in __alloc_gpu (https://github.com/lkoshale/DA_STAR/blob/f17db9039e393f7b67956df51c579790bbd33f23/include/a_star.cu#L72C1-L72C40) rendering all sssp with starting node other than 0 fail to proceed.

Adding gpuErrchk ( cudaMemcpy(d_PQ,PQ,sizeof(unsigned int)*N,cudaMemcpyHostToDevice) ); in __alloc_gpu should fix this issue.

By the way, several cudaFree and free should be added to address device & host memory leaks.

Refer to master...turtleizzy:DA_STAR:master . Several api-breaking features have been added in my fork making it difficult to submit a PR directly from my fork.