def maximal_independent_set(G, nodes=None):
 if (not nodes):
  nodes = set([random.choice(list(G))])
 else:
  nodes = set(nodes)
 if (not nodes.issubset(G)):
  raise nx.NetworkXUnfeasible(('%s is not a subset of the nodes of G' % nodes))
 neighbors = set.union(*[set(G.neighbors(v)) for v in nodes])
 if set.intersection(neighbors, nodes):
  raise nx.NetworkXUnfeasible(('%s is not an independent set of G' % nodes))
 indep_nodes = list(nodes)
 available_nodes = set(G.nodes()).difference(neighbors.union(nodes))
 while available_nodes:
  node = random.choice(list(available_nodes))
  indep_nodes.append(node)
  available_nodes.difference_update((list(G.neighbors(node)) + [node]))
 return indep_nodes

def maximal_independent_set ( G , nodes = None ) : if ( not nodes ) : nodes = set ( [ random . choice ( list ( G ) ) ] ) else : nodes = set ( nodes ) if ( not nodes . issubset ( G ) ) : raise nx . NetworkXUnfeasible ( ( '%s is not a subset of the nodes of G' % nodes ) ) neighbors = set . union ( * [ set ( G . neighbors ( v ) ) for v in nodes ] ) if set . intersection ( neighbors , nodes ) : raise nx . NetworkXUnfeasible ( ( '%s is not an independent set of G' % nodes ) ) indep_nodes = list ( nodes ) available_nodes = set ( G . nodes ( ) ) . difference ( neighbors . union ( nodes ) ) while available_nodes : node = random . choice ( list ( available_nodes ) ) indep_nodes . append ( node ) available_nodes . difference_update ( ( list ( G . neighbors ( node ) ) + [ node ] ) ) return indep_nodes
return a random maximal independent set guaranteed to contain a given set of nodes .