Re: [igraph] Memory issues with igraph-python get_subisomorphisms_vf2
You can just take the vertices that *are* in the subgraph isomorphism, and subtract them (as a set) from all vertices. This is a single setdiff call in R I believe. Gabor On Sep 13, 2015 10:45 PM, "Tamas Nepusz" wrote: > > I can see that the algorithm can very quickly assess if there is a > subgraph isomorphism. > > Could I use this algorithm to extract the information on which vertices > (edges incident with them) do not obey the subgraph isomorphism? > I don't think there it - the original VF2 implementation does not seem > to reveal this information and igraph only provides a wrapper on top > of the original VF2 implementation that allows us to use it with > igraph graphs. > > Best regards, > T. > > ___ > igraph-help mailing list > igraph-help@nongnu.org > https://lists.nongnu.org/mailman/listinfo/igraph-help > ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] Memory issues with igraph-python get_subisomorphisms_vf2
> I can see that the algorithm can very quickly assess if there is a subgraph > isomorphism. > Could I use this algorithm to extract the information on which vertices > (edges incident with them) do not obey the subgraph isomorphism? I don't think there it - the original VF2 implementation does not seem to reveal this information and igraph only provides a wrapper on top of the original VF2 implementation that allows us to use it with igraph graphs. Best regards, T. ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
Re: [igraph] Memory issues with igraph-python get_subisomorphisms_vf2
Thank you, the enumeration by count_subisomorphisms_vf2 reveals the
combinatorial explosion.
A somewhat unrelated question:
Using the get_subisomorphisms_vf2 is there a way to obtain the information on
which links (edges) / vertices cause the subgraph to fail the subgraph
isomorphism definition?
I can see that the algorithm can very quickly assess if there is a subgraph
isomorphism.
Could I use this algorithm to extract the information on which vertices (edges
incident with them) do not obey the subgraph isomorphism?
Thanks!
From: igraph-help-bounces+iva.pritisanac=magd.ox.ac...@nongnu.org
[igraph-help-bounces+iva.pritisanac=magd.ox.ac...@nongnu.org] on behalf of
igraph-help-requ...@nongnu.org [igraph-help-requ...@nongnu.org]
Sent: 10 September 2015 17:01
To: igraph-help@nongnu.org
Subject: igraph-help Digest, Vol 110, Issue 10
Send igraph-help mailing list submissions to
igraph-help@nongnu.org
To subscribe or unsubscribe via the World Wide Web, visit
https://lists.nongnu.org/mailman/listinfo/igraph-help
or, via email, send a message with subject or body 'help' to
igraph-help-requ...@nongnu.org
You can reach the person managing the list at
igraph-help-ow...@nongnu.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of igraph-help digest..."
Today's Topics:
1. Re: Memory issues with igraph-python get_subisomorphisms_vf2
(Szabolcs Horv?t)
2. Memory management of igraph_vector_t in C (Hadidi, Lars)
3. Re: Memory management of igraph_vector_t in C (Tamas Nepusz)
4. rewire (Qunawei Zhang)
--
Message: 1
Date: Wed, 9 Sep 2015 18:42:59 +0200
From: Szabolcs Horv?t
To: Help for igraph users
Subject: Re: [igraph] Memory issues with igraph-python
get_subisomorphisms_vf2
Message-ID:
Content-Type: text/plain; charset="utf-8"
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
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
> igraph-help@nongnu.org
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>
-- next part --
An HTML attachment was scrubbed...
URL:
<http://lists.nongnu.org/archive/html/igraph-help/attachments/20150909/e02aedc4/attachment.html>
--
Message: 2
Date: Wed, 9 Sep 2015 17:53:33 +
From: "Hadidi, Lars"
To: "igraph-help@nongnu.org"
Subject: [igraph] Memory management of igraph_vector_t in C
Message-ID: <1441821213242.85...@students.uni-mainz.de>
Content-Type: text/plain; charset="iso-8859-1"
When using the igraph_vector_t type, it needs to be initialized with the
function igraph_vector_init?, which takes the amount of elements to be
initialized as an argument. The documentation says, that the size of vectors
will be handles automatically by increasing their size on demand, but not using
free when they decrease, in order to keep performance. Therefore, some internal
management must be done. My question is, if it is possible to overestimate the
size of the v
Re: [igraph] Memory issues with igraph-python get_subisomorphisms_vf2
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 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 > igraph-help@nongnu.org > https://lists.nongnu.org/mailman/listinfo/igraph-help > > ___ igraph-help mailing list igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
[igraph] Memory issues with igraph-python get_subisomorphisms_vf2
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 igraph-help@nongnu.org https://lists.nongnu.org/mailman/listinfo/igraph-help
