Найти клики длины k в графе

Question

Я работаю с графиками ~ 200 узлов и ~ 3500 ребер. Мне нужно найти все клики этого графика. Использование network44's enumerate_all_cliques() прекрасно работает с меньшими графиками до 100 узлов, но у них больше памяти для больших.

«Этот алгоритм, однако, надеюсь, не выбегать из памяти , так как он только держит кандидат подсписков в памяти и непрерывно удаляет отработанные подсписки.» source code for enumerate_all_cliques()

Возможно, есть способ вернуть генератор всех клик длиной k, а не всех клик, чтобы сохранить память?

Answer 1

Кажется, что ваш приоритет - сохранить память, а не получать все клики. В этом случае использование networkx.find_cliques(G) является удовлетворительным решением, так как вы получите все максимальные клики (самый большой полный подграф, содержащий данный узел), а не все клики.

Я сравнил количество списков (подграфов) обеих функций:

G = nx.erdos_renyi_graph(300,0.08) print 'All:',len(list(nx.enumerate_all_cliques(G))) print 'Maximal',len(list(nx.find_cliques(G)))

Все: 6087

Максимальная 2522

И когда число ребер увеличивается на графике разница в результатах становится шире.