Re: [igraph] Memory management issue

[Vincent Matossian]

 Thanks for your prompt response Gabor!

I have gone through a few implementations to obtain neighborhood views. In this one I maintain the distance to each original vertex using the 'steps' and 'order' variables. 

Basically, the neighbors are appended to the processing queue only till one step before the desired level is reached (immediate neighbors are added by default), at which point all the neighbors of the vertices still in the queue are popped and added to the final 'view' of the vertex. 

I don't know how I came up with this implementation, it was late and I thought it made sense...I still think it does, but I agree that it's not obvious :)

Anyhow, I am  fresh to R and particularly its development in C, so the file that I have attached (
neighborhood.c) is a very primitive test for the renamed neighborhood function. The main function creates a straight line and my test code might not be very telling. I still don't know how to create better test cases in C alone. 

I could also attach the .R file and corresponding rinterface and namespace components, but I'm not sure how it would be best done. Is it best to create a whole independent package that extends igraph, or  just send the files? I'm still reading the Writing R extensions to figure these things out, sorry for not providing appropriately testable code, please let me know what's best.

Btw, thanks for the recommendation for the renaming, I realized only later that visitors was approprately named for graph traversals. I have now renamed my call to neighborhood. Also, I would certainly not object adding neighborhood to igraph, once the resulting high number of subgraph creation memory issue gets resolved.

Thanks again, keep me posted,

Vincent

On 11/20/06, Gabor Csardi <address@hidden> wrote:

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


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

neighborhood.c
Description: Text document