cugraph.dask.traversal.bfs.bfs#

cugraph.dask.traversal.bfs.bfs(input_graph, start, depth_limit=None, return_distances=True, check_start=True)[source]#

Find the distances and predecessors for a breadth-first traversal of a graph. The input graph must contain edge list as a dask-cudf dataframe with one partition per GPU.

Parameters:
input_graphcugraph.Graph

cuGraph graph instance, should contain the connectivity information as dask cudf edge list dataframe (edge weights are not used for this algorithm).

startInteger or list or cudf object or dask_cudf object

The id(s) of the graph vertex from which the traversal begins in each component of the graph. Only one vertex per connected component of the graph is allowed.

depth_limitInteger or None, optional (default=None)

Limit the depth of the search

return_distancesbool, optional (default=True)

Indicates if distances should be returned

check_startbool, 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 (Only if return_distances is True)

df[‘predecessor’] gives the vertex 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",
...                          blocksize=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.bfs(dg, 0)