python - Method to split a SciPy minimum spanning tree based on greatest edge weight? -

python - Method to split a SciPy minimum spanning tree based on greatest edge weight? -

is there way split output of scipy.sparse.csgraph.minimum_spanning_tree operation dropping greatest border weight value in tree? trying access each of subtrees result dropping greatest border weight if border not outer border of minimum spanning tree.

using scipy docs example:

from scipy.sparse import csr_matrix scipy.sparse.csgraph import minimum_spanning_tree x = csr_matrix([[0, 8, 0, 3], [0, 0, 2, 5], [0, 0, 0, 6], [0, 0, 0, 0]]) tcsr = minimum_spanning_tree(x) # print(tcsr) # (0,3) 3.0 # (3,1) 5.0 # (1,2) 2.0

what best way drop middle value in minimum spanning tree above , have access other 2 edges separately? trying on big graphs , trying avoid big python loops possible. thanks.

i had same problem , managed figure out solution using scipy. take mst, locate maximum weighted edge, delete (i.e. 0 out), , utilize connected_components method figure out nodes remain connected.

here finish script comments:

import numpy np scipy.sparse.csgraph import minimum_spanning_tree, connected_components scipy.sparse import csr_matrix # create random "distance" matrix. # select upper triangle since distance matrix array symmetrical. = np.random.rand(5,5) = np.triu(a) # create minimum spanning tree. mst = minimum_spanning_tree(csr_matrix(a)) mst = mst.toarray() # index of maximum value. # `argmax` returns index of _flattened_ array; # `unravel_index` converts back. idx = np.unravel_index(mst.argmax(), mst.shape) # clear out maximum value split tree. mst[idx] = 0 # label connected components. num_graphs, labels = connected_components(mst, directed=false) # should have 2 trees. assert(num_graphs == 2) # utilize indices node ids , grouping them according graph. results = [[] in range(max(labels) + 1)] idx, label in enumerate(labels): results[label].append(idx) print(results)

this yield like:

[[0, 1, 4], [2, 3]]

python numpy scipy minimum-spanning-tree