[igraph] Memory management issue

[Vincent Matossian]

 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;
}