- 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  (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, https://www.scielo.br/j/pope/a/XHswBwRwJyrfL88dmMwYNWp/?lang=en
- __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_partitionshould 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.