convert minimum spanning tree to list of indices using scipy?

user_5304917 0
Viewed 119

If I have the following input and output graphs

 input graph             minimum spanning tree

     (0)                         (0)
    /   \                       /
   3     8                     3
  /       \                   /
(3)---5---(1)               (3)---5---(1)
  \       /                           /
   6     2                           2
    \   /                           /
     (2)                         (2)

... created using scipy.sparse.csgraph.minimum_spanning_tree:

>>> from scipy.sparse import csr_matrix
>>> from 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)
>>> Tcsr.toarray().astype(int)
array([[0, 0, 0, 3],
       [0, 0, 2, 5],
       [0, 0, 0, 0],
       [0, 0, 0, 0]])

How do I produce a simple list of indices? So:

[0,3,1,2]
data-science scipy sparse-matrix python-3.x python
1 Answers

scipy.sparse.csgraph contains methods to list nodes in depth-first or breadth-first order:

from scipy.sparse.csgraph import breadth_first_order, depth_first_order

print(breadth_first_order(Tcsr, i_start=0, directed=False, return_predecessors=False))
# [0 3 1 2]
print(depth_first_order(Tcsr, i_start=0, directed=False, return_predecessors=False))
# [0 3 1 2]

Since your tree has only a single branch, the two methods produce equivalent results. But for more general spanning trees, you should choose the method based on which traversal order you're interested in.

user_29378310
Related