class Edmonds(G, seed=None)[source]#

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

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


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.



J. Edmonds, Optimum Branchings, Journal of Research of the National Bureau of Standards, 1967, Vol. 71B, p.233-240,

__init__(G, seed=None)[source]#


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

Returns a branching from G.