cugraph.bfs_edges#

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.

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.
sourceInteger: 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

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_edges(G, 0)