pythongraph-theoryrapidscudf

How to convert vertex-predecessor dataframe to path?

I am using cuGraph to do calculate the shortest path of a graph but instead of returning the shortest path to a particular vertex, it creates a distance-vertex-predecessor table:


        distance    vertex  predecessor
3935    0.000000    0       -1
3372    0.063761    1       173
3136    0.059330    2       236
395     0.096309    3       131
3780    0.078157    4       222
... ... ... ...
3886    0.157694    4886    4817
3062    0.226340    4887    4871
3895    0.171506    4888    4816
3057    0.165199    4889    4842
3898    0.213998    4890    4888

How can I get the path to a particular vertex using this graph?

I know I can just loop through it until I get to vertex 0, but this doesn't sound efficient. Is there a way to use vectorization to keep it efficient?

Solution

  • currently the only way is to walk the returned data from target back to source. There is a utility called get_traversed_path(df, id) to simplify that. We recently merged new CUDA code to extract the path a lot faster (cuGraph PR 1838) We are working on adding the python wrapper around that and should have a new feature soon