greedy_branching#
- greedy_branching(G, attr='weight', default=1, kind='max', seed=None)[source]#
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.