@not_implemented_for('directed')
@not_implemented_for('multigraph')
def cycle_basis(G, root=None):
 gnodes = set(G.nodes())
 cycles = []
 while gnodes:
  if (root is None):
   root = gnodes.pop()
  stack = [root]
  pred = {root: root}
  used = {root: set()}
  while stack:
   z = stack.pop()
   zused = used[z]
   for nbr in G[z]:
    if (nbr not in used):
     pred[nbr] = z
     stack.append(nbr)
     used[nbr] = set([z])
    elif (nbr == z):
     cycles.append([z])
    elif (nbr not in zused):
     pn = used[nbr]
     cycle = [nbr, z]
     p = pred[z]
     while (p not in pn):
      cycle.append(p)
      p = pred[p]
     cycle.append(p)
     cycles.append(cycle)
     used[nbr].add(z)
  gnodes -= set(pred)
  root = None
 return cycles

@ not_implemented_for ( 'directed' ) @ not_implemented_for ( 'multigraph' ) def cycle_basis ( G , root = None ) : gnodes = set ( G . nodes ( ) ) cycles = [ ] while gnodes : if ( root is None ) : root = gnodes . pop ( ) stack = [ root ] pred = { root : root } used = { root : set ( ) } while stack : z = stack . pop ( ) zused = used [ z ] for nbr in G [ z ] : if ( nbr not in used ) : pred [ nbr ] = z stack . append ( nbr ) used [ nbr ] = set ( [ z ] ) elif ( nbr == z ) : cycles . append ( [ z ] ) elif ( nbr not in zused ) : pn = used [ nbr ] cycle = [ nbr , z ] p = pred [ z ] while ( p not in pn ) : cycle . append ( p ) p = pred [ p ] cycle . append ( p ) cycles . append ( cycle ) used [ nbr ] . add ( z ) gnodes -= set ( pred ) root = None return cycles
returns a list of cycles which form a basis for cycles of g .