greedy_branching

greedy_branching(G, attr='weight', default=1, kind='max', seed=None)

Returns a branching obtained through a greedy algorithm.

This algorithm is wrong, and cannot give a proper optimal branching. However, we include it for pedagogical reasons, as it can be helpful to see what its outputs are.

The output is a branching, and possibly, a spanning arborescence. However, it is not guaranteed to be optimal in either case.

Parameters

GDiGraph

The directed graph to scan.

attrstr

The attribute to use as weights. If None, then each edge will be treated equally with a weight of 1.

defaultfloat

When attr is not None, then if an edge does not have that attribute, default specifies what value it should take.

kindstr

The type of optimum to search for: ‘min’ or ‘max’ greedy branching.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Returns

Bdirected graph

The greedily obtained branching.