class ArborescenceIterator(G, weight='weight', minimum=True, init_partition=None)[source]#

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


This iterator uses the partition scheme from [1] (included edges, excluded edges and open edges). It generates minimum spanning arborescences using a modified Edmonds’ Algorithm which respects the partition of edges. For arborescences 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, init_partition=None)[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.

init_partitiontuple, default = None

In the case that certain edges have to be included or excluded from the arborescences, init_partition should be in the form (included_edges, excluded_edges) where each edges is a (u, v)-tuple inside an iterable such as a list or set.