spaghetti.spanning_tree¶

spaghetti.spanning_tree(net, method='sort', maximum=False, silence_warnings=True)[source]¶

Extract a minimum or maximum spanning tree from a network.

Parameters:

netspaghetti.Network: Instance of a network object.
methodstr: Method for determining spanning tree. Currently, the only supported method is ‘sort’, which sorts the network arcs by length prior to building intermediary networks and checking for cycles within the tree/subtrees. Future methods may include linear programming approachs, etc.
maximumbool: When True a maximum spanning tree is created. When False a minimum spanning tree is created. Default is False.
silence_warningsbool: Warn if there is more than one connected component. Default is False due to the nature of constructing a minimum spanning tree.

Returns:

netspaghetti.Network: Pruned instance of the network object.

See also

networkx.algorithms.tree.mst
scipy.sparse.csgraph.minimum_spanning_tree

Notes

For in-depth background and details see [GH85], [AMO93], and [OS12d].

Examples

Create a network instance.

>>> from libpysal import cg
>>> import spaghetti
>>> p00 = cg.Point((0,0))
>>> lines = [cg.Chain([p00, cg.Point((0,3)), cg.Point((4,0)), p00])]
>>> ntw = spaghetti.Network(in_data=lines)

Extract the minimum spanning tree.

>>> minst_net = spaghetti.spanning_tree(ntw)
>>> min_len = sum(minst_net.arc_lengths.values())
>>> min_len
7.0

Extract the maximum spanning tree.

>>> maxst_net = spaghetti.spanning_tree(ntw, maximum=True)
>>> max_len = sum(maxst_net.arc_lengths.values())
>>> max_len
9.0

>>> max_len > min_len
True