Skip to main content
`Ctrl`+`K`

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

      The directed graph to scan.

    attr str

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

    default float

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

    kind str

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

    seed integer, random_state, or None (default)

      Indicator of random number generation state. See Randomness.

  Returns:
    B directed graph

      The greedily obtained branching.