igraph-help
[Top][All Lists]

## Re: [igraph] problem with igraph_get_all_shortest_paths

 From: Tamás Nepusz Subject: Re: [igraph] problem with igraph_get_all_shortest_paths Date: Sun, 3 Jul 2011 11:04:35 +0200

Hi,

I've also checked your code with valgrind and it seems okay (no memory leaks etc), so if you think that your graph definitely does not contain that many shortest paths that would justify the memory consumption, send me your graph and I'll try to figure our what's going on here.

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