Skip to main content
`Ctrl`+`K`

# cycle_basis

cycle_basis(G, root=None)

  Returns a list of cycles which form a basis for cycles of G.

  A basis for cycles of a network is a minimal collection of cycles such that any cycle in the network can be written as a sum of cycles in the basis. Here summation of cycles is defined as “exclusive or” of the edges. Cycle bases are useful, e.g. when deriving equations for electric circuits using Kirchhoff’s Laws.

  Parameters:
    G NetworkX Graph
    root node, optional

      Specify starting node for basis.

  Returns:
    A list of cycle lists. Each cycle list is a list of nodes
    which forms a cycle (loop) in G.

  See also

  `simple_cycles`
  `minimum_cycle_basis`

  Notes

  This is adapted from algorithm CACM 491 [1].

  References

  [1]

  Paton, K. An algorithm for finding a fundamental set of cycles of a graph. Comm. ACM 12, 9 (Sept 1969), 514-518.

  Examples

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