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

Question

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

"Однако этот алгоритм, надеемся, не исчерпает память, поскольку он только сохраняет список кандидатов в память и постоянно удаляет исчерпанные списки". исходный код для 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

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