1 files changed, 134 insertions, 0 deletions
diff --git a/src/utils/cum_distr.c b/src/utils/cum_distr.c
new file mode 100644
index 0000000..1445323
--- /dev/null
+++ b/src/utils/cum_distr.c
@@ -0,0 +1,134 @@
+/**
+ *  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 3 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, see
+ *  <http://www.gnu.org/licenses/>.
+ *
+ *  (c) Vincenzo Nicosia 2009-2017 -- <v.nicosia@qmul.ac.uk>
+ * 
+ *  This file is part of NetBunch, a package for complex network
+ *  analysis and modelling. For more information please visit:
+ *
+ *             http://www.complex-networks.net/
+ *
+ *  If you use this software, please add a reference to 
+ *
+ *               V. Latora, V. Nicosia, G. Russo             
+ *   "Complex Networks: Principles, Methods and Applications"
+ *              Cambridge University Press (2017) 
+ *                ISBN: 9781107103184
+ *
+ ***********************************************************************
+ *
+ *  Implementation of a data structure to maintain a cumulative
+ *  distribution and sample values from it. Used in all the models of
+ *  growing graphs based on some kind of preferential attachment.
+ * 
+ */
+
+
+
+#include <stdlib.h>
+#include <stdio.h>
+#include "cum_distr.h"
+
+
+
+cum_distr_t* cum_distr_init(unsigned int N){
+
+  cum_distr_t* d = NULL;
+
+  d = malloc(sizeof(cum_distr_t));
+  
+  d->N = N;
+  d->num = 0;
+  d->sum = 0;
+
+  d->v = malloc((d->N) * sizeof(idval_t));
+  
+  return d;
+}
+
+
+int cum_distr_add(cum_distr_t *d, unsigned int id, long double val){
+  
+  idval_t *tmp;
+
+  if (d->num == d->N){
+    //fprintf(stderr, "+++++++++ REALLOC ++++++++++\n");
+    d->N += 10;
+    tmp = realloc(d->v, d->N * sizeof(idval_t));
+    if (!tmp){
+      d->N -= 10;
+      fprintf(stderr, "#### Error!!! Unable to add more values to the cumulative distribution!!!\n");
+      return -1;
+    }
+    else{
+      d->v = tmp;
+    }
+  }
+  
+  d->sum += val;
+  d->v[d->num].id = id;
+  d->v[d->num].value = d->sum;
+  d->num += 1;
+  //fprintf(stderr, ">>>>>> update >>>>>> d->num: %d\n", d->num);
+  return 0;
+
+}
+
+
+
+/* sample an id from the cumulative distribution, by means of binary
+   search */
+unsigned int cum_distr_sample(cum_distr_t *d){
+  
+  long double val;
+  unsigned int high, low, cur;
+  
+  val = d->sum * rand() / RAND_MAX;
+  
+  cur = d->num / 2;
+  
+  low = 0;
+  high = d->num - 1;
+
+  while (low < high){
+    if (d->v[cur].value < val){
+      low = cur+1;
+    }
+    else if(d->v[cur].value >= val){
+      high = cur;
+    }
+    cur = (high + low) / 2;
+  }
+  return d->v[cur].id;
+}
+
+
+
+void cum_distr_dump(cum_distr_t *d){
+  
+  unsigned int i;
+  
+  
+  for(i=0; i< d->num; i++){
+    fprintf(stderr, "(%d, %g)\n", d->v[i].id, (double)(d->v[i].value));
+  }
+}
+
+
+void cum_distr_destroy(cum_distr_t *d){
+  
+  free(d->v);
+  free(d);
+}