networkx.algorithms.tree.branchings.Edmonds

class Edmonds(G, seed=None)

Edmonds algorithm [1] for finding optimal branchings and spanning arborescences.

This algorithm can find both minimum and maximum spanning arborescences and branchings.

Notes

While this algorithm can find a minimum branching, since it isn’t required to be spanning, the minimum branching is always from the set of negative weight edges which is most likely the empty set for most graphs.

References

1

J. Edmonds, Optimum Branchings, Journal of Research of the National Bureau of Standards, 1967, Vol. 71B, p.233-240, https://archive.org/details/jresv71Bn4p233

__init__(G, seed=None)

Methods

find_optimum([attr, default, kind, style, ...])

Returns a branching from G.