cugraph.bfs_edges(G, source, reverse=False, depth_limit=None, sort_neighbors=None)[source]#

Find the distances and predecessors for a breadth first traversal of a graph.

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.


The starting vertex index

reverseboolean, optional (default=False)

If a directed graph, then process edges in a reverse direction Currently not implemented

depth_limitInt or None, optional (default=None)

Limit the depth of the search

sort_neighborsNone or Function, optional (default=None)

Currently not implemented

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

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.


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