cugraph.dask.traversal.sssp.sssp#

cugraph.dask.traversal.sssp.sssp(input_graph, source, cutoff=None, check_source=True)[source]#

Compute the distance and predecessors for shortest paths from the specified source to all the vertices in the input_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. The input graph must contain edge list as dask-cudf dataframe with one partition per GPU.

Parameters:

input_graphcugraph.Graph: cuGraph graph descriptor, should contain the connectivity information as dask cudf edge list dataframe.
sourceInteger: Specify source vertex
cutoffdouble, optional (default = None): Maximum edge weight sum considered by the algorithm
check_sourcebool, optional (default=True): If True, performs more extensive tests on the start vertices to ensure validitity, at the expense of increased run time.

Returns:

dfdask_cudf.DataFrame

df[‘vertex’] gives the vertex id

df[‘distance’] gives the path distance from the starting vertex

df[‘predecessor’] gives the vertex id it was reached from in the traversal

Examples

>>> import cugraph.dask as dcg
>>> import dask_cudf
>>> # ... Init a DASK Cluster
>>> #    see https://docs.rapids.ai/api/cugraph/stable/dask-cugraph.html
>>> # Download dataset from https://github.com/rapidsai/cugraph/datasets/..
>>> chunksize = dcg.get_chunksize(datasets_path / "karate.csv")
>>> ddf = dask_cudf.read_csv(datasets_path / "karate.csv",
...                          chunksize=chunksize, delimiter=" ",
...                          names=["src", "dst", "value"],
...                          dtype=["int32", "int32", "float32"])
>>> dg = cugraph.Graph(directed=True)
>>> dg.from_dask_cudf_edgelist(ddf, source='src', destination='dst',
...                            edge_attr='value')
>>> df = dcg.sssp(dg, 0)