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 <[email protected]> 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 > [email protected] > https://lists.nongnu.org/mailman/listinfo/igraph-help > >
_______________________________________________ igraph-help mailing list [email protected] https://lists.nongnu.org/mailman/listinfo/igraph-help
