Re: [igraph] Memory management issue

[Gabor Csardi]

Vincent,

i took a look at the code and while i don't know why the memory issues
occur, i noticed that you only put the vertices in the dqueue, but not their
distance from the source vertex. This way i think it is not possible to find
out how far the actual vertex (actnode) is from the source vertex. (In
_decompose this is not an issue since it does not matter how far it is.)
So i think either you need to put the distance into the queue or use some
other data structure for bookkeeping. Or i'm missing something, of course
this might happen as well....

I'll have more time to look at it in the evening (evening US time). Btw. do
you mind if i add your function to igraph (if we can manage to correct the
memory issue, of cource)? Probably it should be called igraph_neighborhood,
or something like this, the _visitor is a bit misleading i think.

Another thing, please consider sending some piece of working code next time,
it is easier for me to try to run it. I mean some r interface code and R
code which fails for you or a small C program; i assume that you have these
already written and this i don't need to rewrite them to see whether the
code works.

Best,
Gabor

On Mon, Nov 20, 2006 at 04:16:21PM -0500, Vincent Matossian wrote:
> 
>  Hi,
> 
> I recently wrote a function that gathers kth order neighborhood views of a
> graph and returns as many subgraphs as there are vertices.
> On large graphs the function in R was pretty slow and I thought I would write
> it in C to see if it would be faster....
> 
> So I wrote the C equivalent into my igraph source, the code runs fine for 
> small
> graphs (<100), but I have not been able to even run the code on large graphs
> (say more than 1000 vertices) because of memory allocation issues, the code
> returns
> 
>                   Error in visitor(grg, 0) : At vector.c:932 : canot copy
> vector, Out of memory
> 
> As I develop in R for Windows, I check the process performance using Process
> Explorer and see the memory handling shoot off the roof within seconds of
> running the code (it scavenges all there is up to 2GB and then errs in R so to
> speak).
> 
> visitor is the name of my function that I've pasted below.
> 
> The function I wrote is *very* similar to igraph_decompose,  that I 
> extensively
> used as model to write igraph_visitor.
> 
> I am wondering where my code is failing. If anyone has a clue please let me
> know, I would greatly appreciate it
> 
> Much Thanks
> 
> Vincent
> 
> Here's the code for igraph_visitor, I added it to rinterface.c in a way 
> exactly
> similar to igraph_decompose. igraph_i_visitor_free is basically
> igraph_i_decompose_free.
> 
> int igraph_visitor(const igraph_t *graf, igraph_vector_ptr_t *res, int order){
>   igraph_t *newg;
>   igraph_dqueue_t q=IGRAPH_DQUEUE_NULL;
>   igraph_vector_t tmp=IGRAPH_VECTOR_NULL;
>   igraph_vector_t view;
>   long int no_of_nodes=igraph_vcount(graf);
>   int steps=0;
>   long int i,j;
>   char* already_processed;
> 
>   already_processed=Calloc(no_of_nodes, char);
>   if (already_processed==0) {
>     IGRAPH_ERROR("Failure in visiting subgraphs", IGRAPH_ENOMEM);
>   }
>   IGRAPH_FINALLY(igraph_free, already_processed); 
>   IGRAPH_CHECK(igraph_dqueue_init(&q, 100));
>   IGRAPH_VECTOR_INIT_FINALLY(&tmp, 0);
>   IGRAPH_VECTOR_INIT_FINALLY(&view,0);
>   igraph_vector_ptr_clear(res);
>   IGRAPH_FINALLY(igraph_i_visitor_free, res);
> 
>   for(i=0;i<no_of_nodes;i++){
>     IGRAPH_ALLOW_INTERRUPTION();
>     memset(already_processed,0,no_of_nodes);
>     already_processed[i]=1;
>     igraph_vector_clear(&view);
>     IGRAPH_CHECK(igraph_dqueue_push(&q,i));
>     IGRAPH_CHECK(igraph_vector_push_back(&view, i));
>     steps=0;
>     while (!igraph_dqueue_empty(&q)) {
>       long int actnode=(long int)igraph_dqueue_pop(&q);
>       IGRAPH_CHECK(igraph_neighbors(graf, &tmp, actnode, IGRAPH_ALL));
>       for (j=0; j<igraph_vector_size(&tmp); j++) {
>     long int neighbor=VECTOR(tmp)[j];
>     if(already_processed[neighbor]!=1){
>       IGRAPH_CHECK(igraph_vector_push_back(&view, neighbor));
>       if(steps<order){
>         IGRAPH_CHECK(igraph_dqueue_push(&q, neighbor));
>       }
>     }
>       }
>       steps++;
>       already_processed[actnode]=1;
>     }
>  
>     newg=Calloc(1,igraph_t);
>     if (newg==0) {
>       IGRAPH_ERROR("Failure in visiting graph", IGRAPH_ENOMEM);
>     }
>     IGRAPH_CHECK(igraph_vector_ptr_push_back(res, newg));
>     IGRAPH_FINALLY(igraph_destroy, newg);
>     IGRAPH_CHECK(igraph_subgraph(graf, newg,igraph_vss_vector(&view)));
>     IGRAPH_FINALLY_CLEAN(1);
>   }
> 
>   igraph_dqueue_destroy(&q);
>   igraph_vector_destroy(&view);
>   igraph_vector_destroy(&tmp);
>   igraph_free(already_processed);
>   IGRAPH_FINALLY_CLEAN(4);
> 
>   return 0;
> }
> 
> 

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


-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK