Skip to main content
`Ctrl`+`K`

# 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:
      G nx.DiGraph

        The directed graph which we need to iterate trees over

      weight String, default = “weight”

        The edge attribute used to store the weight of the edge

      minimum bool, default = True

        Return the trees in increasing order while true and decreasing order while false.

      init_partition tuple, 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