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.

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