networkx.algorithms.tree.branchings.ArborescenceIterator

class ArborescenceIterator(G, weight='weight', minimum=True, init_partition=None)

Iterate over all spanning arborescences 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). 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.

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, init_partition=None)

Initialize the iterator

Parameters:

Gnx.DiGraph

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.

Methods