cugraph.multi_source_bfs#

cugraph.multi_source_bfs( G, sources, components=None, depth_limit=None, offload=False, )[source]#

Find the breadth first traversal from multiple sources in a graph.

Parameters:

Gcugraph.Graph

The adjacency list will be computed if not already present.

sourcescudf.Series

Subset of vertices from which the traversals start. A BFS is run for each source in the Series. The size of the series should be at least one and cannot exceed the size of the graph.

depth_limitInteger, optional, default=None

Limit the depth of the search. Terminates if no more vertices are reachable within the distance of depth_limit

componentscudf.DataFrame, optional, default=None

GPU Dataframe containing the component information. Passing this information may impact the return type. When no component information is passed BFS uses one component behavior settings.

components[‘vertex’]cudf.Series: vertex IDs
components[‘color’]cudf.Series: component IDs/color for vertices.

offloadboolean, optional, default=False

Indicates if output should be written to the disk. When not provided, the algorithms decides if offloading is needed based on the input parameters.

Returns:

Return value type is decided based on the input parameters (size of

sources, size of the graph, number of components and offload setting)

If G is a cugraph.Graph, returns

cudf.DataFrame

df[‘vertex’] vertex IDs

df[‘distance_<source>’] path distance for each vertex from the starting vertex. One column per source.

df[‘predecessor_<source>’] for each i’th position in the column, the vertex ID immediately preceding the vertex at position i in the ‘vertex’ column. One column per source.

If G is a cugraph.Graph and component information is present returns

BFS_edge_listscudf.DataFrame: GPU data frame containing all BFS edges
source_offsets: cudf.Series: Series containing the starting offset in the returned edge list for each source.

If offload is True, or if the output does not fit in memory

Writes csv files containing BFS output to the disk.