如何将顶点前身数据帧转换为路径？

Question

我正在使用 cuGraph 来计算图形的最短路径，但它没有返回到特定顶点的最短路径，而是创建了距离顶点前驱 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

如何使用此图获取到特定顶点的路径？

我知道我可以循环遍历它直到到达顶点 0，但这听起来效率不高。有没有办法使用矢量化来保持高效？

Answer 1

目前唯一的方法是将返回的数据从目标返回到源。有一个名为 get_traversed_path(df, id) 的实用程序可以简化它。我们最近合并了新的 CUDA 代码以更快地提取路径（cuGraph PR 1838）我们正在努力添加 python 包装器并且应该很快就会有一个新功能

如何将顶点前身数据帧转换为路径？

How to convert vertex-predecessor dataframe to path?

python

graph-theory

rapids

cudf