Skip to main content
`Ctrl`+`K`

# minimum_cycle_basis

minimum_cycle_basis(G, weight=None)

  Returns a minimum weight cycle basis for G

  Minimum weight means a cycle basis for which the total weight (length for unweighted graphs) of all the cycles is minimum.

  Parameters:
    G NetworkX Graph
    weight: string

      name of the edge attribute to use for edge weights

  Returns:
    A list of cycle lists. Each cycle list is a list of nodes
    which forms a cycle (loop) in G. Note that the nodes are not
    necessarily returned in a order by which they appear in the cycle

  See also

  `simple_cycles`, `cycle_basis`

  Examples

      >>> G = nx.Graph()
      >>> nx.add_cycle(G, [0, 1, 2, 3])
      >>> nx.add_cycle(G, [0, 3, 4, 5])
      >>> nx.minimum_cycle_basis(G)
      [[5, 4, 3, 0], [3, 2, 1, 0]]

  References:

    [1] Kavitha, Telikepalli, et al. “An O(m^2n) Algorithm for Minimum Cycle Basis of Graphs.” http://link.springer.com/article/10.1007/s00453-007-9064-z [2] de Pina, J. 1995. Applications of shortest path methods. Ph.D. thesis, University of Amsterdam, Netherlands