cugraph.bfs#

cugraph.bfs(G, start=None, depth_limit=None, i_start=None, directed=None, return_predecessors=True)[source]#

Find the distances and predecessors for a breadth first traversal of a graph. Unlike SSSP, BFS supports unweighted graphs.

Parameters:

Gcugraph.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.

startInteger or list, optional (default=None)

The id of the graph vertex from which the traversal begins, or if a list, the 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

i_startInteger, optional (default=None)

Identical to start, added for API compatibility. Only start or i_start can be set, not both.

directedbool, optional (default=None)

NOTE: For non-Graph-type (eg. sparse matrix) values of G only. Raises TypeError if used with a Graph object.

If True, then convert the input matrix to a directed cugraph.Graph, otherwise an undirected cugraph.Graph object will be used.

return_predecessorsbool, optional (default=True)

Whether to return the predecessors for each vertex (returns -1 for each vertex otherwise)

Returns:

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

returns:

cudf.DataFrame

df[‘vertex’] vertex IDs

df[‘distance’] path distance for each vertex from the starting vertex

df[‘predecessor’] for each i’th position in the column, the vertex ID immediately preceding the vertex at position i in the ‘vertex’ column

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.

…or if return_sp_counter is True, returns a 3-tuple with the above two arrays plus:

sp_counter: cupy or numpy ndarray: ndarray of number of shortest paths leading to each vertex.

Examples

>>> from cugraph.datasets import karate
>>> G = karate.get_graph(download=True)
>>> df = cugraph.bfs(G, 0)