Re: [igraph] memory problem(?) in largest clique finding

[Tamas Nepusz]

Hi Sinan,

Thanks for reporting this issue. Actually, the igraph_i_find_k_cliques
function is very uneconomic yet in terms of memory :( The cause of the
issue is the following: when looking for k-cliques, igraph first
collects all k-1-cliques and then tries to merge them pairwise into
k-cliques. We had the assumption that if we have n k-1-cliques, then
we can have at most n*(n-1)/2 k-cliques (when we are able to merge all
pairs of k-1-cliques). This is a _very_ rough upper limit on the
memory needed, and we'll rewrite igraph_i_find_k_cliques to be more
sparing.
In the meanwhile, you might try using igraph_maximal_cliques and see
if you succeed with that. igraph_maximal_cliques uses a different
approach and it returns all maximal (i.e. nonextendable) cliques.
Since all largest cliques are nonextendable, you'll be able to find
the largest cliques among the maximal ones by looking for the ones
that have the most vertices in them.

-- 
Tamas