python - Finding maximal cliques and removing nodes? -

i trying find maximal cliques set of items.

currently using networkx library of python , using find_cliques() function find maximal cliques below:

import newtworkx nx  g = nx.graph() e = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [2,6], [2,5], [5,6]]  g.add_edges_from(e) #g.edges()  lst = list(nx.find_cliques(g)) lst  out [] : [[2, 1, 3, 4], [2, 5, 6]] 

but expecting find maximal cliques , remove nodes in maximal clique graph, , again find maximal clique out of nodes left after previous removal.

for above example, expecting [2, 1, 3, 4] , remove these nodes, 5 , 6 left, clique [5, 6] .

update

we can use g.remove_node(), removes node adjacent edges expected.

g = nx.graph() e = [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [2,6], [2,5], [5,6], [3,5], [5,7]] g.add_edges_from(e)  list1 = list(nx.find_cliques(g)) #list1   gives [[2, 3, 1, 4], [2, 3, 5], [2, 6, 5], [7, 5]]  n = nx.number_of_nodes(g) #n  [g.remove_node(nd) nd in list1[0]] list2 = list(nx.find_cliques(g)) #list2    gives [[5, 6], [5, 7]]  [g.remove_node(nd) nd in list2[0]] list3 = list(nx.find_cliques(g)) #list3    gives [[7]] 

but every time nodes removed, new maximal cliques found , stored in new list , on. how can run in while loop until there no edge left in graph g i.e number of nodes 0 or 1.

you can use g.remove_node remove nodes (and associated edges) graph.

how remove nodes of first clique:

lst = list(nx.find_cliques(g)) [g.remove_node(nd) nd in lst[0]] 

to repeatedly remove nodes of first clique, until no cliques left:

lst = list(nx.find_cliques(g)) while len(lst) > 0:     [g.remove_node(nd) nd in lst[0]]     lst = list(nx.find_cliques(g)) 

note not same removing all nodes in any maximal clique at each step, be:

lst = list(nx.find_cliques(g)) while len(lst) > 0:      # flattens list of cliques 1 list. `set` reduces unique values.     flattened = set([nd cl in lst nd in cl])      [g.remove_node(nd) nd in flattened]     lst = list(nx.find_cliques(g)) 

finally, if there order in remove cliques (e.g. maximum clique first), sorting lst accordingly:

lst = list(nx.find_cliques(g)) while len(lst) > 0:     lst.sort(key=len, reverse=true)       # sort maximum clique front     [g.remove_node(nd) nd in lst[0]]     lst = list(nx.find_cliques(g)) 

edit: completeness sake, here's how 1 store cliques before deleting them (as per comment, @ankie):

out = [] lst = list(nx.find_cliques(g)) while len(lst) > 0:     out.append(lst[0])     [g.remove_node(nd) nd in lst[0]]     lst = list(nx.find_cliques(g)) 

as additional note should pointed out these operations 'destroy' graph g. if graph needed again later on , takes long time construct, makes sense work on copy of graph original preserved. copy can made this:

g2 = g.copy()