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

[Iva Pritisanac]

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: address@hidden address@hidden on behalf of address@hidden address@hidden
Sent: 10 September 2015 17:01
To: address@hidden
Subject: igraph-help Digest, Vol 110, Issue 10

Send igraph-help mailing list submissions to
        address@hidden

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
        address@hidden

You can reach the person managing the list at
        address@hidden

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 <address@hidden>
To: Help for igraph users <address@hidden>
Subject: Re: [igraph] Memory issues with igraph-python
        get_subisomorphisms_vf2
Message-ID:
        <address@hidden>
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 <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
>
>
-------------- 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 +0000
From: "Hadidi, Lars" <address@hidden>
To: "address@hidden" <address@hidden>
Subject: [igraph] Memory management of igraph_vector_t in C
Message-ID: <address@hidden>
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 vector on initialization and assigning elements less then the 
initialization size ? Will the internal management keep track of that, and will 
the algorithms perform correctly on such vectors. I try to avoid memory 
allocation inside the main loop of my program.?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: 
<http://lists.nongnu.org/archive/html/igraph-help/attachments/20150909/b37b361b/attachment.html>

------------------------------

Message: 3
Date: Wed, 9 Sep 2015 20:52:34 +0200
From: Tamas Nepusz <address@hidden>
To: Help for igraph users <address@hidden>
Subject: Re: [igraph] Memory management of igraph_vector_t in C
Message-ID:
        <address@hidden>
Content-Type: text/plain; charset=UTF-8

Hi,

For igraph vectors, one has to distinguish between their _actual_ size
(i.e. the number of elements they hold) and their _capacity_ (i.e. the
maximum number of elements that they can hold without having to
re-allocate the internal memory area that backs the vector). When you
call igraph_vector_init, you set the _actual_ size of the vector - so,
if you pass N as the vector size, the vector will have N
(uninitialized) real elements. What you probably need is to initialize
the vector with zero size and then call igraph_vector_reserve(), which
increases (or decreases) the _capacity_ of the vector while keeping
its size (length) intact.

T.

T.


On Wed, Sep 9, 2015 at 7:53 PM, Hadidi, Lars
<address@hidden> wrote:
> 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 vector on initialization and assigning elements
> less then the initialization size ? Will the internal management keep track
> of that, and will the algorithms perform correctly on such vectors. I try to
> avoid memory allocation inside the main loop of my program.
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>



------------------------------

Message: 4
Date: Thu, 10 Sep 2015 09:21:20 -0400
From: Qunawei Zhang <address@hidden>
To: Help for igraph users <address@hidden>
Subject: [igraph] rewire
Message-ID: <address@hidden>
Content-Type: text/plain; charset="us-ascii"

Hello:

I have some questions about rewire, would you please explain to me? Thanks
(1) Each iteration, two edges are randomly selected right? And the new edges
(which generated by the rewiring) can also be selected and to be rewire
again?
(2) If I set  niter = 100, does it mean 100 edge pairs will be rewired? Is
there a probability that controls whether to rewire each selected edge
pairs? Some times a randomly selected edge pair can not be rewired, will
this counted a trial or only successfully rewired ones will be counted as a
trail?
(3) Sometimes, the rewired network will be divided into several components,
even when the original network is one connected component. Is there is a way
to control the rewire process make the network connected? I tried to just
selected the connected random network, but I can only get a few from 1000
random network, and I need much more.

 rewire(graph, mode = c("simple", "loops"), niter = 100)
niterNumber of rewiring trials to perform.


Thanks.

Best
Quanwei


-------------- next part --------------
An HTML attachment was scrubbed...
URL: 
<http://lists.nongnu.org/archive/html/igraph-help/attachments/20150910/1de51fe6/attachment.html>

------------------------------

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


End of igraph-help Digest, Vol 110, Issue 10
********************************************