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:
- net
spaghetti.Network
Instance of a network object.
- method
str
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. WhenFalse
a minimum spanning tree is created. Default isFalse
.- silence_warningsbool
Warn if there is more than one connected component. Default is
False
due to the nature of constructing a minimum spanning tree.
- net
- Returns:
- net
spaghetti.Network
Pruned instance of the network object.
- net
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