Maximal independent vertex set memory usage grows without bound

[Tony Bigbee]

Using igraph 0.5.4 on 32-bit Linux Ubuntu and 32-bit Windows XP running Python 2.7.1.
With relatively small graph (Undirected |V|=100, |E| = 254, undirected, no self referencings and G = G.simplify() invoked first), memory consumption grows without bound when G.maximal_independent_vertex_sets() is invoked using Python. I'm forced to terminate the process because of virtual memory paging from the hard drive due to the exhaustion of main memory (over 1GB is free when the test is started). Many other functions (like centrality measures) on the same graph/data work fine.

I'm unable to test against 0.6 main because of build problems and missing files (have reported to mailing list).

[Tamás Nepusz (ntamas)]

Same with 0.6.

I'm not sure but I guess that the sparsity of your graph is the problem. Consider a graph with 100 vertices that are paired by 50 edges s.t. vertex 2i is connected to vertex 2i+1. This graph would have 2^50 maximal independent vertex sets as you can choose either end of each edge. This will easily exhaust the main memory. Can you please confirm that your actual graph is not likely to have too many independent vertex sets compared to the size of the graph itself?

[Tony Bigbee (tony-bigbee)]

The sparseness of the graph is the source of the behavior--cutting the edges down to 50 yields 61k sets. I tested using 0.6. So I don't think this is a bug.

Perhaps an optional parameter to limit the number of sets generated to deal with these kinds of situations would be useful.

[Tamás Nepusz (ntamas)]

The most Pythonic solution would be to make the result of maximal_independent_vertex_sets() an iterable instead of a list; there would be no need to store all the sets in memory and the user may choose to stop the iteration any time. Unfortunately, this is not an option because maximal_independent_vertex_sets() is implemented in C and it is really complicated to translate that into a Python iterator.

Maybe a better solution would be to allow one to pass a callback function to maximal_independent_vertex_sets(). This would be called for every vertex set the algorithm finds, and its return value would decide whether to keep on searching.

[Gábor Csárdi (gabor.csardi)]

I like the callback solution, we already have that for a couple of algorithms.

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/425