class SpanningTreeIterator(G, weight='weight', minimum=True, ignore_nan=False)[source]#

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


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.



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,

__init__(G, weight='weight', minimum=True, ignore_nan=False)[source]#

Initialize the iterator


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.