pylibcugraph.sssp#
- pylibcugraph.sssp(ResourceHandle resource_handle, _GPUGraph graph, size_t source, double cutoff, bool_t compute_predecessors, bool_t do_expensive_check)[source]#
Compute the distance and predecessors for shortest paths from the specified source to all the vertices in the graph. The returned distances array will contain the distance from the source to each vertex in the returned vertex array at the same index. The returned predecessors array will contain the previous vertex in the shortest path for each vertex in the vertex array at the same index. Vertices that are unreachable will have a distance of infinity denoted by the maximum value of the data type and the predecessor set as -1. The source vertex predecessor will be set to -1. Graphs with negative weight cycles are not supported.
- Parameters:
- resource_handleResourceHandle
Handle to the underlying device resources needed for referencing data and running algorithms.
- graphSGGraph or MGGraph
The input graph, for either Single or Multi-GPU operations.
- source
The vertex identifier of the source vertex.
- cutoff
Maximum edge weight sum to consider.
- compute_predecessorsbool
This parameter must be set to True for this release.
- do_expensive_checkbool
If True, performs more extensive tests on the inputs to ensure validitity, at the expense of increased run time.
- Returns:
- A 3-tuple, where the first item in the tuple is a device array containing
- the vertex identifiers, the second item is a device array containing the
- distance for each vertex from the source vertex, and the third item is a
- device array containing the vertex identifier of the preceding vertex in the
- path for that vertex. For example, the vertex identifier at the ith element
- of the vertex array has a distance from the source vertex of the ith element
- in the distance array, and the preceding vertex in the path is the ith
- element in the predecessor array.
Examples
>>> import pylibcugraph, cupy, numpy >>> srcs = cupy.asarray([0, 1, 2], dtype=numpy.int32) >>> dsts = cupy.asarray([1, 2, 3], dtype=numpy.int32) >>> weights = cupy.asarray([1.0, 1.0, 1.0], dtype=numpy.float32) >>> resource_handle = pylibcugraph.ResourceHandle() >>> graph_props = pylibcugraph.GraphProperties( ... is_symmetric=False, is_multigraph=False) >>> G = pylibcugraph.SGGraph( ... resource_handle, graph_props, srcs, dsts, weight_array=weights, ... store_transposed=False, renumber=False, do_expensive_check=False) >>> (vertices, distances, predecessors) = pylibcugraph.sssp( ... resource_handle, G, source=1, cutoff=999, ... compute_predecessors=True, do_expensive_check=False) >>> vertices array([0, 1, 2, 3], dtype=int32) >>> distances array([3.4028235e+38, 0.0000000e+00, 1.0000000e+00, 2.0000000e+00], dtype=float32) >>> predecessors array([-1, -1, 1, 2], dtype=int32)