/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006 Gabor Csardi <csardi@rmki.kfki.hu> MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #include <stdlib.h> int print_vector(igraph_vector_t *v) { long int i, n=igraph_vector_size(v); for (i=0; i<n; i++) { printf("%li ", (long int) VECTOR(*v)[i]); } printf("\n"); return 0; } int main() { igraph_psumtree_t tree; igraph_vector_t vec; long int i; igraph_real_t sum; /* Uniform random numbers */ igraph_vector_init(&vec, 16); igraph_psumtree_init(&tree, 16); sum=igraph_psumtree_sum(&tree); if (sum != 0) { printf("Sum: %f instead of 0.\n", sum); return 1; } for (i=0; i<16; i++) { igraph_psumtree_update(&tree, i, 1); } if ((sum=igraph_psumtree_sum(&tree)) != 16) { printf("Sum: %f instead of 16.\n", sum); return 2; } for (i=0; i<16000; i++) { igraph_real_t r=((double)rand())/RAND_MAX * sum; long int idx; igraph_psumtree_search(&tree, &idx, r); VECTOR(vec)[idx] += 1; } for (i=0; i<16; i++) { if (VECTOR(vec)[i] < 800 || VECTOR(vec)[i] > 1200) { return 3; } } /* Nonuniform, even indices have twice as much chance */ for (i=0; i<16; i+=2) { igraph_psumtree_update(&tree, i, 2); } if ((sum=igraph_psumtree_sum(&tree)) != 24) { printf("Sum: %f instead of 24.\n", sum); return 4; } igraph_vector_null(&vec); for (i=0; i<24000; i++) { igraph_real_t r=((double)rand())/RAND_MAX * sum; long int idx; igraph_psumtree_search(&tree, &idx, r); VECTOR(vec)[idx] += 1; } for (i=0; i<16; i++) { if (i%2 == 0 && (VECTOR(vec)[i] < 1800 || VECTOR(vec)[i] > 2200)) { return 5; } if (i%2 != 0 && (VECTOR(vec)[i] < 800 || VECTOR(vec)[i] > 1200)) { return 6; } } /* Test zero probabilities */ igraph_psumtree_update(&tree, 0, 0); igraph_psumtree_update(&tree, 5, 0); igraph_psumtree_update(&tree, 15, 0); sum=igraph_psumtree_sum(&tree); igraph_vector_null(&vec); for (i=0; i<20000; i++) { igraph_real_t r=((double)rand())/RAND_MAX * sum; long int idx; igraph_psumtree_search(&tree, &idx, r); VECTOR(vec)[idx] += 1; } if (VECTOR(vec)[0] != 0 || VECTOR(vec)[5] != 0 || VECTOR(vec)[15] != 0) { return 7; } igraph_vector_destroy(&vec); igraph_psumtree_destroy(&tree); /****************************************************/ /* Non power-of-two vector size */ /****************************************************/ igraph_vector_init(&vec, 9); igraph_psumtree_init(&tree, 9); for (i=0; i<9; i++) { igraph_psumtree_update(&tree, i, 1); } sum=igraph_psumtree_sum(&tree); for (i=0; i<9000; i++) { igraph_real_t r=((double)rand())/RAND_MAX * sum; long int idx; igraph_psumtree_search(&tree, &idx, r); VECTOR(vec)[idx] += 1; } for (i=0; i<9; i++) { if (VECTOR(vec)[i] < 800 || VECTOR(vec)[i] > 1200) { return 8; } } /* Nonuniform, even indices have twice as much chance */ for (i=0; i<9; i+=2) { igraph_psumtree_update(&tree, i, 2); } sum=igraph_psumtree_sum(&tree); igraph_vector_null(&vec); for (i=0; i<14000; i++) { igraph_real_t r=((double)rand())/RAND_MAX * sum; long int idx; igraph_psumtree_search(&tree, &idx, r); VECTOR(vec)[idx] += 1; } for (i=0; i<9; i++) { if (i%2 == 0 && (VECTOR(vec)[i] < 1800 || VECTOR(vec)[i] > 2200)) { return 9; } if (i%2 != 0 && (VECTOR(vec)[i] < 800 || VECTOR(vec)[i] > 1200)) { return 10; } } /* Test query */ for (i=0; i<igraph_psumtree_size(&tree); i++) { if (i%2==0 && igraph_psumtree_get(&tree, i) != 2) { return 11; } if (i%2!=0 && igraph_psumtree_get(&tree, i) != 1) { return 12; } } /* Test zero probabilities */ igraph_psumtree_update(&tree, 0, 0); igraph_psumtree_update(&tree, 5, 0); igraph_psumtree_update(&tree, 8, 0); sum=igraph_psumtree_sum(&tree); igraph_vector_null(&vec); for (i=0; i<9000; i++) { igraph_real_t r=((double)rand())/RAND_MAX * sum; long int idx; igraph_psumtree_search(&tree, &idx, r); VECTOR(vec)[idx] += 1; } if (VECTOR(vec)[0] != 0 || VECTOR(vec)[5] != 0 || VECTOR(vec)[8] != 0) { return 11; } igraph_vector_destroy(&vec); igraph_psumtree_destroy(&tree); if (!IGRAPH_FINALLY_STACK_EMPTY) return 13; return 0; }