networkx.algorithms.tree.mst.SpanningTreeIterator

class SpanningTreeIterator(G, weight='weight', minimum=True, ignore_nan=False)

Iterate over all spanning trees of a graph in either increasing or decreasing cost.

Notes

This iterator uses the partition scheme from [1] (included edges, excluded edges and open edges) as well as a modified Kruskal’s Algorithm to generate minimum spanning trees which respect the partition of edges. For spanning trees with the same weight, ties are broken arbitrarily.

References

[1]

G.K. Janssens, K. Sörensen, An algorithm to generate all spanning trees in order of increasing cost, Pesquisa Operacional, 2005-08, Vol. 25 (2), p. 219-229, https://www.scielo.br/j/pope/a/XHswBwRwJyrfL88dmMwYNWp/?lang=en

Examples

SpanningTreeIterator can be used to find all minimum or maximum spanning trees of a graph:

>>> import itertools
>>> G = nx.cycle_graph(3)
>>> trees_by_weight = itertools.groupby(
...     nx.SpanningTreeIterator(G), key=lambda t: t.size(weight="weight")
... )
>>> min_wt, min_wt_trees = next(trees_by_weight)
>>> min_wt
2.0
>>> sorted(t.edges for t in min_wt_trees)
[EdgeView([(0, 1), (0, 2)]), EdgeView([(0, 2), (1, 2)]), EdgeView([(0, 1), (1, 2)])]

The minimum=False option yields trees by weight in descending order:

>>> G = nx.Graph()
>>> G.add_edge("A", "B", weight=3)
>>> G.add_edge("A", "C", weight=2)
>>> G.add_edge("B", "C", weight=1)
>>> trees_by_weight = itertools.groupby(
...     nx.SpanningTreeIterator(G, minimum=False),
...     key=lambda t: t.size(weight="weight"),
... )
>>> max_wt, max_wt_trees = next(trees_by_weight)
>>> max_wt
5.0
>>> sorted(t.edges for t in max_wt_trees)
[EdgeView([('A', 'B'), ('A', 'C')])]

__init__(G, weight='weight', minimum=True, ignore_nan=False)

Initialize the iterator

Parameters:

Gnx.Graph

The directed graph which we need to iterate trees over

weightString, default = “weight”

The edge attribute used to store the weight of the edge

minimumbool, default = True

Return the trees in increasing order while true and decreasing order while false.

ignore_nanbool, default = False

If a NaN is found as an edge weight normally an exception is raised. If ignore_nan is True then that edge is ignored instead.

Methods