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

__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