cugraph.sssp

cugraph.sssp(G, source=None, method=None, directed=None, return_predecessors=None, unweighted=None, overwrite=None, indices=None, cutoff=None, edge_attr='weight')

Compute the distance and predecessors for shortest paths from the specified source to all the vertices in the graph. The distances column will store the distance from the source to each vertex. The predecessors column will store each vertex’s predecessor in the shortest path. 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’s predecessor is also set to -1. Graphs with negative weight cycles are not supported. Unweighted graphs are also unsupported.

For finding shortest paths on an unweighted graph, use BFS instead.

Parameters:

graphcugraph.Graph, networkx.Graph, CuPy or SciPy sparse matrix Graph or

matrix object, which should contain the connectivity information. Edge weights, if present, should be single or double precision floating point values. The current implementation only supports weighted graphs.

sourceint

Index of the source vertex.

cutoffdouble, optional (default=None)

Maximum edge weight sum considered by the algorithm

edge_attrstr, optional (default=’weight’)

The name of the edge attribute that represents the weight of an edge. This currently applies only when G is a NetworkX Graph. Default value is ‘weight’, which follows NetworkX convention.

Returns:

Return value type is based on the input type. If G is a cugraph.Graph,

returns:

cudf.DataFrame

df[‘vertex’]

vertex id

df[‘distance’]

gives the path distance from the starting vertex

df[‘predecessor’]

the vertex it was reached from

If G is a networkx.Graph, returns:

pandas.DataFrame with contents equivalent to the cudf.DataFrame described above.

If G is a CuPy or SciPy matrix, returns:

a 2-tuple of CuPy ndarrays (if CuPy matrix input) or Numpy ndarrays (if SciPy matrix input) representing:

distance: cupy or numpy ndarray

ndarray of shortest distances between source and vertex.

predecessor: cupy or numpy ndarray

ndarray of predecessors of a vertex on the path from source, which can be used to reconstruct the shortest paths.

Examples

>>> from cugraph.datasets import karate
>>> G = karate.get_graph(download=True)
>>> distances = cugraph.sssp(G, 0)
>>> distances
        distance  vertex  predecessor
...       ...     ...         ...
...       ...     ...         ...
...       ...     ...         ...