pylibcugraph.minimum_spanning_tree#

pylibcugraph.minimum_spanning_tree( ResourceHandle resource_handle, _GPUGraph graph, do_expensive_check=False, )[source]#

Extract a minimum spanning tree (MST) or forest (MSF) on an undirected graph

Parameters:

resource_handleResourceHandle: Handle to the underlying device resources needed for referencing data and running algorithms.
graphSGGraph or MGGraph: The input graph.
do_expensive_checkbool (default=True): If True, performs more extensive tests on the inputs to ensure validitity, at the expense of increased run time.

Returns:

A tuple of device arrays containing the sources, destinations,
edge_weights and edge_offsets.

Examples

>>> import pylibcugraph, cupy, numpy
>>> srcs = cupy.asarray([0, 1, 1, 2, 2, 2, 3, 4, 1, 3, 4,
...     0, 1, 3, 5, 5], dtype=numpy.int32)
>>> dsts = cupy.asarray([1, 3, 4, 0, 1, 3, 5, 5, 0, 1, 1,
...     2, 2, 2, 3, 4], dtype=numpy.int32)
>>> weights = cupy.asarray(
...     [0.1, 2.1, 1.1, 5.1, 3.1, 4.1, 7.2, 3.2, 0.1, 2.1,
...     1.1, 5.1, 3.1, 4.1, 7.2, 3.2]
...     ,dtype=numpy.float32)
>>> resource_handle = pylibcugraph.ResourceHandle()
>>> graph_props = pylibcugraph.GraphProperties(
...     is_symmetric=True, is_multigraph=False)
>>> G = pylibcugraph.SGGraph(
...     resource_handle, graph_props, srcs, dsts, weight_array=weights,
...     store_transposed=False, renumber=False, do_expensive_check=False)
>>> (sources, destinations, edge_weights, subgraph_offsets) =
...     pylibcugraph.minimum_spanning_tree(resource_handle, G, False)
>>> sources
array([0, 1, 2, 3, 4, 5, 1, 1, 1, 4], dtype=int32)
>>> destinations
array([1, 0, 1, 1, 1, 4, 2, 3, 4, 5], dtype=int32)
>>> edge_weights
array([0.1, 0.1, 3.1, 2.1, 1.1, 3.2, 3.1, 2.1, 1.1, 3.2], dtype=float32)
>>> subgraph_offsets
array([0, 10])