Re: [igraph] problem with igraph_get_all_shortest_paths

[Tamás Nepusz]

Hi Guilherme,

Your code looks fine at first glance, but not e that it's not the number of nodes that really matters (although it also does) but the number of possible shortest paths between two vertices A and B. For graphs with highly regular structure, it is quite possible that there is a high number of shortest paths between two given nodes A and B, and igraph will try to find all of these with igraph_get_all_shortest paths. For instance, consider a regular 2-dimensional 10x10 lattice. The number of possible shortest paths from the upper left node to the lower right node is 20! / (10! * 10!). If your graph has a similar sub-structure, igraph can easily run out of memory

-- 
T.

On Sunday, 3 July 2011 at 02:32, Guilherme Ferraz de Arruda wrote:

Hi,

I have tryed to make a function to implement the measure proposed at "Networks and cities: An information perspective" by Rosvall et al.
Some times (with some graphs) my program doesnt work well, the memory grows (up to 40Gb, using swap) and the graph has less than 6000 nodes.
I want to know if i'm  using this function correctly


My code is:

// Functions for Information Measure
long int GetValue(igraph_vector_t *v, long int i){
  return (long int) VECTOR(*v)[i];
}

long int GetLastValue(igraph_vector_t *v){
  return (long int) VECTOR(*v)[igraph_vector_size(v)-1];
}

double Ppib(igraph_t* g, igraph_vector_t *v){
  long int ki = 0, kj = 0;
  igraph_vector_t res0;
  igraph_vector_init(&res0, 0);
 
  double acc = 1.0;

  igraph_degree(g, &res0, igraph_vss_1((igraph_integer_t)VECTOR(*v)[0]), IGRAPH_ALL, IGRAPH_NO_LOOPS);
  ki = (double)VECTOR(res0)[0];
  igraph_vector_clear(&res0);
 
  long int l = 0;
  for(l=1; l<igraph_vector_size(v) - 1; l++){   
    igraph_degree(g, &res0, igraph_vss_1((igraph_integer_t)VECTOR(*v)[l]), IGRAPH_ALL, IGRAPH_NO_LOOPS);
    kj = (double)VECTOR(res0)[0];
    igraph_vector_clear(&res0);
   
    acc *= (double)1.0/(double)(kj - 1.0);
  }
 
  igraph_vector_destroy(&res0);
 
  return acc/ki;
}

int CreateSMatrix(igraph_t* g, double** S){
  long int N = igraph_vcount(g);
 
  long int vertice = 0;
  long int i = 0, j = 0, k = 0;
 
    for(vertice=0; vertice<N; vertice++){
    igraph_vector_ptr_t vecs;
    igraph_vector_ptr_init(&vecs, 0);
   
    /*for (i=0; i<igraph_vector_ptr_size(&vecs); i++) {
      VECTOR(vecs)[i] = calloc(1, sizeof(igraph_vector_t));
      igraph_vector_init(VECTOR(vecs)[i], 0);
    }*/
   
    igraph_get_all_shortest_paths(g, &vecs, NULL, vertice, igraph_vss_all(), IGRAPH_ALL);
   
    for (k=0; k<igraph_vector_ptr_size(&vecs); k++) {
      //if(i != k)
      if(GetValue(VECTOR(vecs)[k], 0) != GetLastValue(VECTOR(vecs)[k]))
        //P(p(i,b)
        S[GetValue(VECTOR(vecs)[k], 0)][GetLastValue(VECTOR(vecs)[k])] += Ppib(g, VECTOR(vecs)[k]);
     
      igraph_vector_destroy(VECTOR(vecs)[k]);
      free(VECTOR(vecs)[k]);
    }
   
    igraph_vector_ptr_destroy(&vecs);
   
      }
     
      for(i=0; i<N; i++)
    for(k=0; k<N; k++){
      if(S[i][k] != 0) S[i][k] = (-1)*log2(S[i][k]);
    }
     
      return 1;
}


Thanks for all

Guilherme.

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