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

Question

我使用 cuGraph 来计算图的最短路径，但它不是返回到特定顶点的最短路径，而是创建一个距离顶点前驱表：

        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_pa​​th(df, id)的实用程序可以简化这一过程。我们最近合并了新的 CUDA 代码，以更快地提取路径（cuGraph PR 1838）我们正在努力添加 python 包装器，并且应该很快就会有一个新功能