igraph-help
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Memory issues with igraph-python get_subisomorphisms_vf2


From: Szabolcs Horvát
Subject: Re: [igraph] Memory issues with igraph-python get_subisomorphisms_vf2
Date: Wed, 9 Sep 2015 18:42:59 +0200

Depending on your graphs, there can be potentially a very large number of (sub)isomorphisms.  If you want to store all of them at the same time, the memory requirement is far worse than that.  For an extreme example, consider a complete graph on 2N nodes.  How many complete subgraphs does it contain on N nodes?  For 2N = 40 that would be (2N)! / (2 N!) = 137 846 528 820 ~ 1.38e11.

Have you tried the count_subisomorphisms_vf2 function?  It won't store all isomorphisms, it will only count them.  If there's combinatorial explosion it might still not ever finish in practice though.

In the C interface there's a vf2 function that executes a custom callback function for each isomorphism found.  The callback function can signal that it wants to stop.  With this one can implement finding at most a certain number of isomorphisms and stopping afterwards.  This is what I did with the Mathematica interface (patterned after Mathematica's own isomorphism finder function), though I am not yet sure of what use it will be to find more than one yet less than all of them.



On 9 September 2015 at 16:14, Iva Pritisanac <address@hidden> wrote:
Dear All,

I have memory problem when using igraph-python method get_subisomorphisms_vf2 on Windows 64bit system.

I am using igraph-python in the context of a graph-subgraph isomorphism applications for graph-subgraph with ~40 vertices.
When attempting to obtain a nested list of all subisomorphisms, physical memory of my system gets exhausted very quickly (~within 10min).

Given that the memory requirement of the vf2 algorithm is O(N), I should not have this problem. Is there something I am missing?

Thank you very much in advance!

Sincerely,

Iva
 

_______________________________________________
igraph-help mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/igraph-help



reply via email to

[Prev in Thread] Current Thread [Next in Thread]