← Back to branch summary

~ubuntu-branches/ubuntu/lucid/igraph/lucid

« back to all changes in this revision

Viewing changes to examples/simple/igraph_psumtree.c

  • Committer: Bazaar Package Importer
  • Author(s): Mathieu Malaterre
  • Date: 2009-11-16 18:12:42 UTC
  • Revision ID: james.westby@ubuntu.com-20091116181242-mzv9p5fz9uj57xd1
Tags: upstream-0.5.3
Import upstream version 0.5.3

Show diffs side-by-side

added added

removed removed

Lines of Context:
examples/simple/igraph_psumtree.c
 
1
 
 
2
/* -*- mode: C -*-  */
 
3
/* 
 
4
   IGraph library.
 
5
   Copyright (C) 2006  Gabor Csardi <csardi@rmki.kfki.hu>
 
6
   MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
 
7
   
 
8
   This program is free software; you can redistribute it and/or modify
 
9
   it under the terms of the GNU General Public License as published by
 
10
   the Free Software Foundation; either version 2 of the License, or
 
11
   (at your option) any later version.
 
12
   
 
13
   This program is distributed in the hope that it will be useful,
 
14
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
15
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
16
   GNU General Public License for more details.
 
17
   
 
18
   You should have received a copy of the GNU General Public License
 
19
   along with this program; if not, write to the Free Software
 
20
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
 
21
   02110-1301 USA
 
22
 
 
23
*/
 
24
 
 
25
#include <igraph.h>
 
26
#include <stdlib.h>
 
27
 
 
28
int print_vector(igraph_vector_t *v) {
 
29
  long int i, n=igraph_vector_size(v);
 
30
  for (i=0; i<n; i++) {
 
31
    printf("%li ", (long int) VECTOR(*v)[i]);
 
32
  }
 
33
  printf("\n");
 
34
  return 0;
 
35
}
 
36
 
 
37
int main() {
 
38
  igraph_psumtree_t tree;
 
39
  igraph_vector_t vec;
 
40
  long int i;
 
41
  igraph_real_t sum;
 
42
 
 
43
  /* Uniform random numbers */
 
44
  igraph_vector_init(&vec, 16);
 
45
  igraph_psumtree_init(&tree, 16);
 
46
  sum=igraph_psumtree_sum(&tree);
 
47
  if (sum != 0) {
 
48
    printf("Sum: %f instead of 0.\n", sum);
 
49
    return 1;
 
50
  }
 
51
 
 
52
  for (i=0; i<16; i++) {
 
53
    igraph_psumtree_update(&tree, i, 1);
 
54
  }
 
55
  if ((sum=igraph_psumtree_sum(&tree)) != 16) {
 
56
    printf("Sum: %f instead of 16.\n", sum);
 
57
    return 2;
 
58
  }
 
59
  
 
60
  for (i=0; i<16000; i++) {
 
61
    igraph_real_t r=((double)rand())/RAND_MAX * sum;
 
62
    long int idx;
 
63
    igraph_psumtree_search(&tree, &idx, r);
 
64
    VECTOR(vec)[idx] += 1;
 
65
  }  
 
66
  for (i=0; i<16; i++) {
 
67
    if (VECTOR(vec)[i] < 800 || VECTOR(vec)[i] > 1200) {
 
68
      return 3;
 
69
    }
 
70
  }
 
71
 
 
72
  /* Nonuniform, even indices have twice as much chance */
 
73
  for (i=0; i<16; i+=2) {
 
74
    igraph_psumtree_update(&tree, i, 2);
 
75
  }
 
76
  if ((sum=igraph_psumtree_sum(&tree)) != 24) {
 
77
    printf("Sum: %f instead of 24.\n", sum);
 
78
    return 4;
 
79
  }
 
80
  
 
81
  igraph_vector_null(&vec);
 
82
  for (i=0; i<24000; i++) {
 
83
    igraph_real_t r=((double)rand())/RAND_MAX * sum;
 
84
    long int idx;
 
85
    igraph_psumtree_search(&tree, &idx, r);
 
86
    VECTOR(vec)[idx] += 1;
 
87
  }
 
88
  for (i=0; i<16; i++) {
 
89
    if (i%2 == 0 && (VECTOR(vec)[i] < 1800 || VECTOR(vec)[i] > 2200)) {
 
90
      return 5;
 
91
    }
 
92
    if (i%2 != 0 && (VECTOR(vec)[i] < 800 || VECTOR(vec)[i] > 1200)) {
 
93
      return 6;
 
94
    }
 
95
  }
 
96
  
 
97
  /* Test zero probabilities */
 
98
  igraph_psumtree_update(&tree, 0, 0);
 
99
  igraph_psumtree_update(&tree, 5, 0);
 
100
  igraph_psumtree_update(&tree, 15, 0);
 
101
  sum=igraph_psumtree_sum(&tree);
 
102
  
 
103
  igraph_vector_null(&vec);
 
104
  for (i=0; i<20000; i++) {
 
105
    igraph_real_t r=((double)rand())/RAND_MAX * sum;
 
106
    long int idx;
 
107
    igraph_psumtree_search(&tree, &idx, r);
 
108
    VECTOR(vec)[idx] += 1;
 
109
  }
 
110
  if (VECTOR(vec)[0] != 0 || VECTOR(vec)[5] != 0 || VECTOR(vec)[15] != 0) {
 
111
    return 7;
 
112
  }
 
113
 
 
114
  igraph_vector_destroy(&vec);
 
115
  igraph_psumtree_destroy(&tree);
 
116
 
 
117
  /****************************************************/
 
118
  /* Non power-of-two vector size                     */
 
119
  /****************************************************/
 
120
 
 
121
  igraph_vector_init(&vec, 9);
 
122
  igraph_psumtree_init(&tree, 9);
 
123
 
 
124
  for (i=0; i<9; i++) {
 
125
    igraph_psumtree_update(&tree, i, 1);
 
126
  }
 
127
  sum=igraph_psumtree_sum(&tree);
 
128
  
 
129
  for (i=0; i<9000; i++) {
 
130
    igraph_real_t r=((double)rand())/RAND_MAX * sum;
 
131
    long int idx;
 
132
    igraph_psumtree_search(&tree, &idx, r);
 
133
    VECTOR(vec)[idx] += 1;
 
134
  }  
 
135
  for (i=0; i<9; i++) {
 
136
    if (VECTOR(vec)[i] < 800 || VECTOR(vec)[i] > 1200) {
 
137
      return 8;
 
138
    }
 
139
  }
 
140
 
 
141
  /* Nonuniform, even indices have twice as much chance */
 
142
  for (i=0; i<9; i+=2) {
 
143
    igraph_psumtree_update(&tree, i, 2);
 
144
  }
 
145
  sum=igraph_psumtree_sum(&tree);
 
146
  
 
147
  igraph_vector_null(&vec);
 
148
  for (i=0; i<14000; i++) {
 
149
    igraph_real_t r=((double)rand())/RAND_MAX * sum;
 
150
    long int idx;
 
151
    igraph_psumtree_search(&tree, &idx, r);
 
152
    VECTOR(vec)[idx] += 1;
 
153
  }
 
154
  for (i=0; i<9; i++) {
 
155
    if (i%2 == 0 && (VECTOR(vec)[i] < 1800 || VECTOR(vec)[i] > 2200)) {
 
156
      return 9;
 
157
    }
 
158
    if (i%2 != 0 && (VECTOR(vec)[i] < 800 || VECTOR(vec)[i] > 1200)) {
 
159
      return 10;
 
160
    }
 
161
  }
 
162
 
 
163
  /* Test query */
 
164
  for (i=0; i<igraph_psumtree_size(&tree); i++) {
 
165
    if (i%2==0 && igraph_psumtree_get(&tree, i) != 2) {
 
166
      return 11;
 
167
    }
 
168
    if (i%2!=0 && igraph_psumtree_get(&tree, i) != 1) {
 
169
      return 12;
 
170
    }
 
171
  }
 
172
  
 
173
  /* Test zero probabilities */
 
174
  igraph_psumtree_update(&tree, 0, 0);
 
175
  igraph_psumtree_update(&tree, 5, 0);
 
176
  igraph_psumtree_update(&tree, 8, 0);
 
177
  sum=igraph_psumtree_sum(&tree);
 
178
  
 
179
  igraph_vector_null(&vec);
 
180
  for (i=0; i<9000; i++) {
 
181
    igraph_real_t r=((double)rand())/RAND_MAX * sum;
 
182
    long int idx;
 
183
    igraph_psumtree_search(&tree, &idx, r);
 
184
    VECTOR(vec)[idx] += 1;
 
185
  }
 
186
  if (VECTOR(vec)[0] != 0 || VECTOR(vec)[5] != 0 || VECTOR(vec)[8] != 0) {
 
187
    return 11;
 
188
  }
 
189
 
 
190
  igraph_vector_destroy(&vec);
 
191
  igraph_psumtree_destroy(&tree);
 
192
 
 
193
  if (!IGRAPH_FINALLY_STACK_EMPTY) return 13;
 
194
  
 
195
  return 0;
 
196
}