summaryrefslogtreecommitdiff
path: root/src/utils
diff options
context:
space:
mode:
Diffstat (limited to 'src/utils')
-rw-r--r--src/utils/cum_distr.c134
-rw-r--r--src/utils/dset.c128
-rw-r--r--src/utils/gen_heap.c302
-rw-r--r--src/utils/gen_pqueue.c359
-rw-r--r--src/utils/gen_stack.c87
-rw-r--r--src/utils/iltree.c291
-rw-r--r--src/utils/iltree_double.c102
-rw-r--r--src/utils/utils.c785
8 files changed, 2188 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);
+}
diff --git a/src/utils/dset.c b/src/utils/dset.c
new file mode 100644
index 0000000..acb6bc8
--- /dev/null
+++ b/src/utils/dset.c
@@ -0,0 +1,128 @@
+/**
+ * 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
+ *
+ ***********************************************************************
+ *
+ * This files implements a disjoint-set data structure, where nodes
+ * labels are integers.
+ *
+ */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "dset.h"
+
+void dset_makeset(dset_t *ds){
+
+ if (*ds == NULL){
+ *ds= malloc(sizeof(dset_elem_t));
+ }
+ (*ds)->parent = *ds;
+ (*ds) -> rank = 0;
+}
+
+void dset_destroy(dset_t ds){
+ free(ds);
+}
+
+
+void dset_makeset_id(dset_t *ds, int id){
+
+ dset_makeset(ds);
+ (*ds)->id = id;
+}
+
+
+dset_t dset_find(dset_t ds){
+ if (ds -> parent == ds){
+ return ds;
+ }
+ else return dset_find(ds->parent);
+}
+
+void dset_union(dset_t s1, dset_t s2){
+ dset_t r1, r2;
+
+ r1= dset_find(s1);
+ r2= dset_find(s2);
+ r2->parent = r1;
+}
+
+
+void dset_union_opt(dset_t s1, dset_t s2){
+ dset_t r1, r2;
+
+ r1= dset_find(s1);
+ r2= dset_find(s2);
+ if (r1 == r2){
+ return;
+ }
+
+ if (r1->rank < r2->rank){
+ r1->parent = r2;
+ }
+ else if (r1->rank > r2->rank){
+ r2->parent = r1;
+ }
+ else{
+ r2->parent = r1;
+ r1->rank += 1;
+ }
+}
+
+
+dset_t dset_find_opt(dset_t ds){
+ if (ds->parent != ds){
+ ds->parent = dset_find_opt(ds->parent);
+ }
+ return ds->parent;
+}
+
+
+int dset_find_id(dset_t ds){
+
+ dset_t res;
+
+ res = dset_find(ds);
+
+ return res->id;
+}
+
+
+int dset_find_id_opt(dset_t ds){
+
+ dset_t res;
+
+ res = dset_find_opt(ds);
+
+ return res->id;
+}
+
diff --git a/src/utils/gen_heap.c b/src/utils/gen_heap.c
new file mode 100644
index 0000000..586c7fd
--- /dev/null
+++ b/src/utils/gen_heap.c
@@ -0,0 +1,302 @@
+/**
+ * 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
+ *
+ ***********************************************************************
+ *
+ * This is an implementation of binary heaps (both Min-Heap and
+ * Max-Heap).
+ *
+ */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include <string.h>
+
+#include "gen_heap.h"
+
+
+
+gen_heap_t * gen_heap_init(unsigned int N, char htype, gen_heap_func_t *funs){
+
+ gen_heap_t* h;
+
+ h = malloc(sizeof(gen_heap_t));
+ h->htype = htype;
+ h->N = N;
+ h->last = -1;
+ h->funs = *funs;
+ h->v = h->funs.alloc_vector(N);
+ return h;
+}
+
+
+void __gen_heap_sift_up(gen_heap_t *h, int i){
+
+ int idx, parent;
+ void *tmp;
+
+ idx = i;
+ parent = PARENT(idx);
+ switch(h->htype){
+ case MAX_HEAP:
+ while ( idx >0 && h->funs.compare(h->v[idx], h->v[parent]) > 0){
+ tmp = h->v[idx];
+ h->v[idx] = h->v[parent];
+ h->v[parent] = tmp;
+ idx = parent;
+ parent = PARENT(idx);
+ }
+ break;
+ case MIN_HEAP:
+ while ( idx >0 && h-> funs.compare(h->v[idx], h->v[parent]) < 0){
+ tmp = h->v[idx];
+ h->v[idx] = h->v[parent];
+ h->v[parent] = tmp;
+ idx = parent;
+ parent = PARENT(idx);
+ }
+ break;
+ }
+}
+
+
+void __gen_heap_sift_down(gen_heap_t *h, int i){
+
+ int left, right, largest, smallest;
+ void *tmp;
+
+
+ switch(h->htype){
+
+ case MAX_HEAP:
+ largest = i;
+ left = 2 * i + 1;
+ right = 2 * i + 2;
+
+ if (left <= h->last && h->funs.compare(h->v[left], h->v[largest]) > 0){
+ largest = left;
+ }
+ if (right <= h->last && h->funs.compare(h->v[right], h->v[largest]) > 0){
+ largest = right;
+ }
+ if (largest != i){
+ tmp = h->v[i];
+ h->v[i] = h->v[largest];
+ h->v[largest] = tmp;
+ __gen_heap_sift_down(h, largest);
+ }
+ break;
+
+ case MIN_HEAP:
+ smallest = i;
+ left = 2 * i + 1;
+ right = 2 * i + 2;
+
+ if (left <= h->last && h->funs.compare(h->v[left], h->v[smallest]) < 0){
+ smallest = left;
+ }
+ if (right <= h->last && h->funs.compare(h->v[right], h->v[smallest]) < 0){
+ smallest = right;
+ }
+ if (smallest != i){
+ tmp = h->v[i];
+ h->v[i] = h->v[smallest];
+ h->v[smallest] = tmp;
+ __gen_heap_sift_down(h, smallest);
+ }
+ break;
+ }
+
+}
+
+
+void gen_heap_insert(gen_heap_t *h, void *elem){
+
+ if (h->last < h->N-1){
+ h->last += 1;
+ h->v[h->last] = elem;
+ }
+ else{
+ fprintf(stderr, "Error! Trying to insert more than %d elements in the heap (%s:%d)\n",
+ h->N, __FILE__, __LINE__);
+ return;
+ }
+ __gen_heap_sift_up(h, h->last);
+}
+
+
+
+int gen_heap_delete(gen_heap_t *h, void **val){
+
+ if (h->last >=0){
+ *val = h->v[0];
+ h->v[0] = h->v[h->last];
+ h->last -= 1;
+ __gen_heap_sift_down(h,0);
+ return 0;
+ }
+ else{
+ return 1;
+ }
+}
+
+
+
+void* gen_heap_peek(gen_heap_t *h){
+ return h->v[0];
+}
+
+
+gen_heap_t* gen_heap_from_array(void **v, unsigned int N, unsigned int last,
+ char htype, gen_heap_func_t *funs){
+
+ gen_heap_t *h;
+ int i;
+
+ h = malloc(sizeof(gen_heap_t));
+ h->N = N;
+ h->last = last;
+ h->htype = htype;
+ h->funs = *funs;
+ h->v = v;
+
+ for (i=last >> 1 ; i>=0; i--){
+ __gen_heap_sift_down(h, i);
+ }
+ return h;
+}
+
+
+
+void gen_heap_dump(gen_heap_t* h){
+
+ int i;
+
+ unsigned int N;
+
+ N = h->last+1;
+
+ printf("N: %d last:%d root:", h->N, h->last);
+ if (h->last >=0)
+ h->funs.print_elem(h->v[0]);
+ else
+ printf("NULL");
+ printf("\n");
+
+ for(i=0; i<N; i++){
+ if (i < (N+1)/2){
+ if (2*i+1 < N)
+ if (2*i + 2 < N){
+ printf("%d: ", i);
+ h->funs.print_elem(h->v[i]);
+ printf(" (");
+ h->funs.print_elem(h->v[2*i+1]);
+ printf(", ");
+ h->funs.print_elem(h->v[2*i+2]);
+ printf(")\n");
+ }
+ else{
+ printf("%d: ", i);
+ h->funs.print_elem(h->v[i]);
+ printf(" (");
+ h->funs.print_elem(h->v[2*i+1]);
+ printf(", NULL)\n");
+ }
+ else{
+ printf("%d: ", i);
+ h->funs.print_elem(h->v[i]);
+ printf(" (NULL, NULL)\n");
+ }
+ }
+ else{
+ printf("%d: ", i);
+ h->funs.print_elem(h->v[i]);
+ printf(" (NULL, NULL)\n");
+ }
+ }
+ printf("\n");
+}
+
+void gen_heap_destroy(gen_heap_t *h){
+
+ int i;
+
+ /* First deallocate all the elems */
+ for(i=0; i<=h->last; i++){
+ h->funs.dealloc_elem(h->v[i]);
+ }
+
+ /* now we deallocate the array */
+ h->funs.dealloc_vector(h->v);
+ h->v = NULL;
+ free(h);
+}
+
+
+int gen_heap_sort(void *v, unsigned int N, size_t size, char dir,
+ int (*compar)(const void *, const void *)){
+
+ gen_heap_func_t funs;
+ gen_heap_t *h;
+ void *val, **new_v=NULL, *tmp_v=NULL;
+ char htype;
+ int i;
+
+ funs.compare = compar;
+
+ htype = MAX_HEAP;
+
+ if (dir == SORT_DESC)
+ htype = MIN_HEAP;
+
+ new_v = malloc(N * sizeof(void*));
+ tmp_v = malloc(N * size);
+
+ for (i=0; i<N; i++){
+ new_v[i] = (char*)v+ i* size;
+ }
+
+ h = gen_heap_from_array(new_v, N, N-1, htype, &funs);
+ for(i = 0; i<N; i++){
+ if (gen_heap_delete(h, (void **)&val)){
+ free(new_v);
+ free(tmp_v);
+ return ERR_DELETE;
+ }
+ //fprintf(stderr, "(%p <- %p) ", (char*) v + (N-i-1) * size, val);
+ memcpy((char*)tmp_v + (N-i-1) * size, val, size);
+ }
+ memcpy(v, tmp_v, N*size);
+ free(new_v);
+ free(tmp_v);
+ return 0;
+}
+
diff --git a/src/utils/gen_pqueue.c b/src/utils/gen_pqueue.c
new file mode 100644
index 0000000..590bb98
--- /dev/null
+++ b/src/utils/gen_pqueue.c
@@ -0,0 +1,359 @@
+/**
+ * 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
+ *
+ ***********************************************************************
+ *
+ * This is an implementation of a (MIN/MAX)-priority-queue based on
+ * gen_heap. Most of the functions, with the only exception of
+ * gen_pqueue_change_key which is the core of the priority queue, are
+ * just wrappers around the corresponding functions in gen_heap
+ *
+ */
+
+
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+
+#include "gen_pqueue.h"
+
+void __update_handle(gen_pqueue_t *q, int idx){
+
+ q->handles[q->funs.get_id(q->v[idx])] = idx;
+}
+
+
+gen_pqueue_t * gen_pqueue_init(unsigned int N, char qtype, gen_pqueue_func_t *funs){
+
+ gen_pqueue_t* q;
+ int i;
+
+ q = malloc(sizeof(gen_pqueue_t));
+ q->qtype = qtype;
+ q->N = N;
+ q->last = -1;
+ q->funs = *funs;
+ q->v = q->funs.alloc_vector(N);
+ q->handles = malloc(N * sizeof(int));
+ for (i=0; i<N; i++){
+ q->handles[i] = -1;
+ }
+ return q;
+
+}
+
+void __gen_pqueue_sift_up(gen_pqueue_t *q, int i){
+
+ int idx, parent;
+ void *tmp;
+
+ idx = i;
+ parent = PARENT(idx);
+
+ switch(q->qtype){
+ case MAX_QUEUE:
+ while ( idx >0 && q->funs.compare(q->v[idx], q->v[parent]) > 0){
+ tmp = q->v[idx];
+ q->v[idx] = q->v[parent];
+ q->v[parent] = tmp;
+ __update_handle(q, idx);
+ __update_handle(q, parent);
+ idx = parent;
+ parent = PARENT(idx);
+ }
+ break;
+ case MIN_QUEUE:
+ while ( idx >0 && q-> funs.compare(q->v[idx], q->v[parent]) < 0){
+ tmp = q->v[idx];
+ q->v[idx] = q->v[parent];
+ q->v[parent] = tmp;
+ __update_handle(q, idx);
+ __update_handle(q, parent);
+ idx = parent;
+ parent = PARENT(idx);
+ }
+ break;
+ }
+}
+
+
+void __gen_pqueue_sift_down(gen_pqueue_t *q, int i){
+
+ int left, right, largest, smallest;
+ void *tmp;
+
+ switch(q->qtype){
+ case MAX_QUEUE:
+ largest = i;
+ left = 2 * i + 1;
+ right = 2 * i + 2;
+
+ if (left <= q->last && q->funs.compare(q->v[left], q->v[largest]) > 0){
+ largest = left;
+ }
+ if (right <= q->last && q->funs.compare(q->v[right], q->v[largest]) > 0){
+ largest = right;
+ }
+ if (largest != i){
+ tmp = q->v[i];
+ q->v[i] = q->v[largest];
+ q->v[largest] = tmp;
+ __update_handle(q, i);
+ __update_handle(q, largest);
+ __gen_pqueue_sift_down(q, largest);
+ }
+ else{
+ __update_handle(q, i);
+ }
+ break;
+
+ case MIN_QUEUE:
+ smallest = i;
+ left = 2 * i + 1;
+ right = 2 * i + 2;
+
+ if (left <= q->last && q->funs.compare(q->v[left], q->v[smallest]) < 0){
+ smallest = left;
+ }
+ if (right <= q->last && q->funs.compare(q->v[right], q->v[smallest]) < 0){
+ smallest = right;
+ }
+ if (smallest != i){
+ tmp = q->v[i];
+ q->v[i] = q->v[smallest];
+ q->v[smallest] = tmp;
+ __update_handle(q, i);
+ __update_handle(q, smallest);
+ __gen_pqueue_sift_down(q, smallest);
+ }
+ else{
+ __update_handle(q, i);
+ }
+ break;
+ }
+}
+
+
+void gen_pqueue_insert(gen_pqueue_t *q, void *elem){
+
+ if (q->last < q->N-1){
+ q->last += 1;
+ q->v[q->last] = elem;
+ __update_handle(q, q->last);
+ }
+ else{
+ fprintf(stderr, "Error! Trying to insert more than %d elements in the heap (%s:%d)\n",
+ q->N, __FILE__, __LINE__);
+ return;
+ }
+ __gen_pqueue_sift_up(q, q->last);
+}
+
+
+
+int gen_pqueue_delete(gen_pqueue_t *q, void **val){
+
+ if (q->last >=0){
+ *val = q->v[0];
+ q->v[0] = q->v[q->last];
+ q->last -= 1;
+ __gen_pqueue_sift_down(q, 0);
+ return 0;
+ }
+ else{
+ return 1;
+ }
+}
+
+
+
+void* gen_pqueue_peek(gen_pqueue_t *q){
+
+ return q->v[0];
+}
+
+gen_pqueue_t* gen_pqueue_from_array(void **v, unsigned int N, unsigned int last, char qtype,
+ gen_pqueue_func_t *funs){
+
+ gen_pqueue_t *q;
+ int i;
+
+ q = gen_pqueue_init(N, qtype, funs);
+ /* FIXME!!!! WARNING!!!! we should associate the array v to the array of the pqueue!!!! */
+ for (i=last >> 1 ; i>=0; i--){
+ __gen_pqueue_sift_down(q, i);
+ }
+ return q;
+}
+
+
+
+
+int gen_pqueue_force_key(gen_pqueue_t *q, unsigned int idx, void *key){
+
+
+ switch(q->qtype){
+ case MAX_QUEUE:
+ if (q->funs.compare_to_key(q->v[idx], key) > 0){
+ q->funs.set_key(q->v[idx], key);
+ __gen_pqueue_sift_down(q, idx);
+ }
+ else{
+ q->funs.set_key(q->v[idx], key);
+ __gen_pqueue_sift_up(q, idx);
+ }
+ break;
+ case MIN_QUEUE:
+ if (q->funs.compare_to_key(q->v[idx], key) < 0){
+ q->funs.set_key(q->v[idx], key);
+ __gen_pqueue_sift_down(q, idx);
+ }
+ else{
+ q->funs.set_key(q->v[idx], key);
+ __gen_pqueue_sift_up(q, idx);
+ }
+ break;
+ }
+ return 0;
+}
+
+
+int gen_pqueue_change_key(gen_pqueue_t *q, unsigned int idx, void *key){
+
+
+ switch(q->qtype){
+ case MAX_QUEUE:
+ if (q->funs.compare_to_key(q->v[idx], key) > 0){
+ return KEY_ERROR; /* we cannot assign a smaller key on a MAX_QUEUE*/
+ }
+ /* If everything is OK, we then set the new key here */
+ q->funs.set_key(q->v[idx], key);
+ if (idx == 0)
+ return 0;
+ __gen_pqueue_sift_up(q, idx);
+ break;
+ case MIN_QUEUE:
+ if (q->funs.compare_to_key(q->v[idx], key) < 0){
+ return KEY_ERROR; /* we cannot assign a higher key on a MIN_QUEUE*/
+ }
+ /* If everything is OK, we then set the new key here */
+ q->funs.set_key(q->v[idx], key);
+ /* parent = (int)(floor((idx-1)/2)); */
+ if (idx == 0)
+ return 0;
+ __gen_pqueue_sift_up(q, idx);
+ break;
+ }
+ return -1;
+}
+
+
+
+void gen_pqueue_dump(gen_pqueue_t *q){
+
+ int i;
+
+ unsigned int N;
+
+ N = q->last+1;
+
+ printf("N: %d last:%d root:", q->N, q->last);
+ if (q->last >=0)
+ q->funs.print_elem(q->v[0]);
+ else
+ printf("NULL");
+ printf("\n");
+
+ for(i=0; i<N; i++){
+ if (i < (N+1)/2){
+ if (2*i+1 < N)
+ if (2*i + 2 < N){
+ printf("%d: ", i);
+ q->funs.print_elem(q->v[i]);
+ printf(" (");
+ q->funs.print_elem(q->v[2*i+1]);
+ printf(", ");
+ q->funs.print_elem(q->v[2*i+2]);
+ printf(")\n");
+ }
+ else{
+ printf("%d: ", i);
+ q->funs.print_elem(q->v[i]);
+ printf(" (");
+ q->funs.print_elem(q->v[2*i+1]);
+ printf(", NULL)\n");
+ }
+ else{
+ printf("%d: ", i);
+ q->funs.print_elem(q->v[i]);
+ printf(" (NULL, NULL)\n");
+ }
+ }
+ else{
+ printf("%d: ", i);
+ q->funs.print_elem(q->v[i]);
+ printf(" (NULL, NULL)\n");
+ }
+ }
+ printf("\n");
+}
+
+
+void gen_pqueue_destroy(gen_pqueue_t *q){
+
+ int i;
+
+ /* First deallocate all the remaining elems (those that have not
+ been deleted) */
+ for(i=0; i<=q->last; i++){
+ q->funs.dealloc_elem(q->v[i]);
+ }
+
+ /* now we deallocate the array of elems */
+ q->funs.dealloc_vector(q->v);
+ free(q->handles);
+ free(q);
+}
+
+
+int gen_pqueue_get_handle(gen_pqueue_t *q, int id){
+
+ if (id >= q->N){
+ return ID_ERROR;
+ }
+ return q->handles[id];
+}
+
+void* gen_pqueue_get_key(gen_pqueue_t *q, int idx){
+
+ return q->funs.get_key(q->v[idx]);
+
+}
diff --git a/src/utils/gen_stack.c b/src/utils/gen_stack.c
new file mode 100644
index 0000000..76d8021
--- /dev/null
+++ b/src/utils/gen_stack.c
@@ -0,0 +1,87 @@
+/**
+ * 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 stack data structure, which stores pointers to
+ * generic objects
+ *
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "gen_stack.h"
+
+void gen_stack_create(gen_stack_t *s){
+
+ s->size = 10;
+ s->head = -1;
+ s->v = malloc(s->size * sizeof(void*));
+
+}
+
+void gen_stack_push(gen_stack_t *s, void *elem){
+
+ //void ** tmp;
+
+ if (s->head == s->size-1){
+ s->size += 10;
+ s->v = realloc(s->v, s->size * sizeof(void*));
+ if (!s->v){
+ fprintf(stderr, "Unable to allocate more memory in stack.c:stack_push... Exiting!\n");
+ exit(17);
+ }
+ }
+ s->head++;
+ s->v[s->head] = elem;
+}
+
+int gen_stack_pop(gen_stack_t *s, void **res){
+
+ if (!gen_stack_empty(s)){
+ *res = s->v[s->head];
+ s->head--;
+ return 0;
+ }
+ else{
+ return -1;
+ }
+
+}
+
+int gen_stack_empty(gen_stack_t *s){
+
+ return (s->head < 0 ? 1 : 0);
+}
+
+
+int gen_stack_size(gen_stack_t *s){
+ return s->head + 1;
+}
diff --git a/src/utils/iltree.c b/src/utils/iltree.c
new file mode 100644
index 0000000..28e8d90
--- /dev/null
+++ b/src/utils/iltree.c
@@ -0,0 +1,291 @@
+/**
+ * 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
+ *
+ ***********************************************************************
+ *
+ * This is an implementation of a simple insert-lookup Binary Search
+ * Tree. It supports adding nodes, checking for the presence of
+ * keys, visiting the BST in pre-order, getting the maximum/minumum
+ * key, and applying a function to all the nodes. There is no support
+ * for deleting nodes.
+ *
+ */
+
+
+/*
+ *
+ * A simple insert-lookup static binary tree datatype
+ *
+ */
+
+#include <stdlib.h>
+#include "iltree.h"
+#include <stdio.h>
+
+
+void __recursive_preorder(node_t *cur, ilfunc_t *funs){
+
+ if(cur->left){
+ __recursive_preorder(cur->left, funs);
+ }
+ funs->print(cur->info, funs->fileout);
+ if(cur->right){
+ __recursive_preorder(cur->right, funs);
+ }
+}
+
+/*
+ *
+ * Recursive push of nodes in the nodecache :-)
+ *
+ */
+
+void __recursive_destroy(node_t *cur, ilfunc_t *funs){
+ if(cur->left){
+ __recursive_destroy(cur->left, funs);
+ free(cur->left);
+ cur->left = NULL;
+ }
+ if(cur->right){
+ __recursive_destroy(cur->right, funs);
+ free(cur->right);
+ cur->right = NULL;
+ }
+ funs->dealloc(cur->info);
+}
+
+
+int __recursive_insert(node_t *cur, node_t *elem, ilfunc_t *f){
+
+ int res ;
+ res = f->compare(cur->info, elem->info);
+ /* printf("res: %d\n", res); */
+ if ( res > 0){
+ if (cur->left){
+ return __recursive_insert(cur->left, elem, f);
+ }
+ else{
+ cur->left = elem;
+ return 0;
+ }
+ }
+ else if (res < 0){
+ if (cur->right){
+ return __recursive_insert(cur->right, elem, f);
+ }
+ else{
+ cur->right = elem;
+ return 0;
+ }
+ }
+ printf("warning!!!!! duplicate entry!!!!!!\n\n");
+ return -1;
+}
+
+
+
+void* __recursive_lookup(node_t *cur, void *v, ilfunc_t *f){
+
+ int res;
+
+ res = f->compare(cur->info, v);
+
+ if (res > 0){
+ if(cur->left)
+ return __recursive_lookup(cur->left, v, f);
+ else
+ return NULL;
+
+ }
+ else if (res < 0){
+ if(cur->right)
+ return __recursive_lookup(cur->right, v, f);
+ else
+ return NULL;
+ }
+ else
+ return cur->info;
+}
+
+void __recursive_map(node_t *cur, void (*func)(void*)){
+
+ if (cur->left)
+ __recursive_map(cur->left, func);
+ func(cur->info);
+ if (cur->right)
+ __recursive_map(cur->right, func);
+}
+
+void __recursive_map_args(node_t *cur, void (*func)(void*, void*), void *args){
+
+ if (cur->left)
+ __recursive_map_args(cur->left, func, args);
+ func(cur->info, args);
+ if (cur->right)
+ __recursive_map_args(cur->right, func, args);
+}
+
+
+
+iltree_t iltree_create(iltree_t t){
+ if (!t) {
+ t = (iltree_t)malloc(sizeof(iltree_struct_t));
+ }
+ t->root = NULL;
+ return t;
+}
+
+
+void iltree_set_funs(iltree_t t, ilfunc_t *funs){
+
+ t->funs = *funs;
+}
+
+
+void iltree_insert(iltree_t t, void *elem){
+
+ node_t *n;
+
+ n = (node_t*)malloc(sizeof(node_t));
+ n->info = t->funs.alloc();
+ t->funs.copy(elem, n->info);
+ n->left = n->right = NULL;
+ if (t->root == NULL){
+ t->root = n;
+ }
+ else{
+ __recursive_insert(t->root, n, & (t->funs));
+ }
+}
+
+
+void iltree_destroy(iltree_t t){
+
+ if(t->root)
+ __recursive_destroy(t->root, & (t->funs));
+ free(t->root);
+ free(t);
+}
+
+
+
+
+void iltree_view_pre(iltree_t t){
+
+ if (t->root){
+ /*printf("----\n");*/
+ __recursive_preorder(t->root, & (t->funs));
+ /*printf("----\n");*/
+ }
+ else
+ printf("----- Empty tree!!!! -----\n");
+
+}
+
+
+
+void* iltree_lookup(iltree_t t , void *elem){
+
+ if(t->root)
+ return __recursive_lookup(t->root, elem, & (t->funs) );
+ else
+ return NULL;
+}
+
+
+void iltree_map(iltree_t t, void (*func)(void*)){
+
+ __recursive_map(t->root, func);
+
+}
+
+
+void iltree_map_args(iltree_t t, void (*func)(void*, void*), void *args){
+
+ __recursive_map_args(t->root, func, args);
+
+}
+
+void* iltree_get_fileout(iltree_t t){
+
+ return t->funs.fileout;
+}
+
+void iltree_set_fileout(iltree_t t, void *f){
+
+ t->funs.fileout = f;
+}
+
+void* __recursive_getmin(node_t *cur){
+
+ if(cur->left){
+ return __recursive_getmin(cur->left);
+ }
+ else{
+ return cur->info;
+ }
+
+}
+
+
+void* iltree_getmin(iltree_t t){
+
+ if (!t){
+ return NULL;
+ }
+ else{
+ return __recursive_getmin(t->root);
+ }
+
+}
+
+
+void* __recursive_getmax(node_t *cur){
+
+ if(cur->right){
+ return __recursive_getmax(cur->right);
+ }
+ else{
+ return cur->info;
+ }
+
+}
+
+
+void* iltree_getmax(iltree_t t){
+
+ if (!t){
+ return NULL;
+ }
+ else{
+ return __recursive_getmax(t->root);
+ }
+
+}
+
diff --git a/src/utils/iltree_double.c b/src/utils/iltree_double.c
new file mode 100644
index 0000000..a22236d
--- /dev/null
+++ b/src/utils/iltree_double.c
@@ -0,0 +1,102 @@
+/**
+ * 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 the iltree data structure with keys of type
+ * "long double"
+ *
+ */
+
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+#include "iltree_double.h"
+
+
+void* alloc_double(){
+ return malloc(sizeof(long double));
+}
+
+void dealloc_double(void *elem){
+ free(elem);
+}
+
+void copy_double(void *elem1, void *elem2){
+ *((long double*)elem2) = *((long double*)elem1);
+}
+
+
+int compare_long_double(void *elem1, void *elem2){
+
+ long double *l1, *l2;
+
+ l1 = (long double*)elem1;
+ l2 = (long double*)elem2;
+
+ return (*l1 < *l2 ? -1 : (*l1 > *l2 ? 1 : 0));
+ //return *((long double*)elem1) - *((long double*)elem2);
+}
+
+void print_long_double(void *elem, void *fileout){
+
+ long double k, i, j;
+ long double x;
+
+ k = *((long double*)elem);
+
+ x = (1 + sqrtl(1 + 8 * (k-1))) / 2;
+ i = floorl(x) + 1;
+ j = k - ( (i-1)*1.0 * (i-2) ) /2;
+ //printf("x: %Lf\n i: %0.0Lf j: %0.0Lf\n", x, i, j);
+ fprintf((FILE*)fileout, "%d %d\n", (unsigned int)(i-1), (unsigned int)(j-1));
+}
+
+iltree_t iltree_double_init(iltree_t t, void *fileout){
+
+ ilfunc_t funs= {
+ .alloc = alloc_double,
+ .dealloc = dealloc_double,
+ .copy = copy_double,
+ .compare = compare_long_double,
+ .print = print_long_double,
+ .fileout = fileout
+ };
+
+ t = iltree_create(t);
+ iltree_set_funs(t, &funs);
+ return t;
+}
+
+
+void iltree_double_dump_edges(iltree_t t){
+
+ iltree_view_pre(t);
+}
diff --git a/src/utils/utils.c b/src/utils/utils.c
new file mode 100644
index 0000000..6ed5c19
--- /dev/null
+++ b/src/utils/utils.c
@@ -0,0 +1,785 @@
+/**
+ * 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
+ *
+ ***********************************************************************
+ *
+ * This file contains general utilities to handle input/output of
+ * graphs, convert between different sparse matrix representations,
+ * and other ancillary functions. It is linked against most of the
+ * programs in NetBunch.
+ *
+ */
+
+
+
+#include <stdlib.h>
+#include <math.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+
+#include "utils.h"
+
+
+
+/* Read a degree distribution -- OBSOLETE */
+int read_deg_distr(FILE *filein, unsigned int **degs, unsigned int **Nk, double **p){
+
+ int n_degs = 0;
+ int size = 10;
+ char buff[256];
+ int k_i, num_i;
+ double p_i;
+ char *ptr;
+
+
+ *degs = realloc(*degs, size*sizeof(unsigned int));
+ *Nk = realloc(*Nk, size*sizeof(unsigned int));
+ *p = realloc(*p, size*sizeof(double));
+
+
+ while(fgets(buff, 256, filein)){
+ ptr = strtok(buff, " ");
+ VALID_PTR_OR_EXIT(ptr, 7);
+ if (ptr[0] == '#')
+ continue;
+ k_i = atoi(ptr);
+ ptr = strtok(NULL, " " );
+ VALID_PTR_OR_EXIT(ptr, 7);
+ num_i = atoi(ptr);
+ ptr = strtok(NULL, " \n");
+ VALID_PTR_OR_EXIT(ptr, 7);
+ p_i = atof(ptr);
+ if (n_degs == size){
+ size += 10;
+ *degs = realloc(*degs, size*sizeof(unsigned int));
+ *Nk = realloc(*Nk, size*sizeof(unsigned int));
+ *p = realloc(*p, size*sizeof(double));
+ }
+ (*degs)[n_degs] = k_i;
+ (*Nk)[n_degs] = num_i;
+ (*p)[n_degs] = p_i;
+ n_degs += 1;
+ }
+ if (n_degs > 0){
+ *degs = realloc(*degs, n_degs*sizeof(unsigned int));
+ *Nk = realloc(*Nk, n_degs*sizeof(unsigned int));
+ *p = realloc(*p, n_degs*sizeof(double));
+ }
+ return n_degs;
+}
+
+
+int read_deg_seq(FILE *filein, unsigned int **nodes){
+
+ int size, N, k;
+ char buff[256];
+ char *ptr;
+
+ N = 0;
+ size = 10;
+
+ *nodes = (unsigned int*)malloc(size * sizeof(unsigned int));
+
+ while(fgets(buff, 256, filein)){
+ ptr = strtok(buff, " ");
+ VALID_PTR_OR_EXIT(ptr, 7);
+ if (ptr[0] == '#')
+ continue;
+ k = atoi(ptr);
+
+ if (N == size){
+ size += 10;
+ *nodes = realloc(*nodes, size*sizeof(unsigned int));
+ }
+ (*nodes)[N] = k;
+ N += 1;
+ }
+ if (N > 0)
+ *nodes = realloc(*nodes, N * sizeof(unsigned int));
+ return N;
+}
+
+int read_stubs(FILE *filein, unsigned int **S){
+
+ int size, K;
+ char buff[256];
+ char *ptr;
+
+ K=0;
+ size = 20;
+ *S = malloc(size * sizeof(unsigned int));
+
+ while(fgets(buff, 256, filein)){
+ if (K == size){
+ size += 20;
+ *S = realloc(*S, size*sizeof(unsigned int));
+ }
+ ptr = strtok(buff, " "); /* read the first node */
+ VALID_PTR_OR_EXIT(ptr, 7);
+ (*S)[K++] = atoi(ptr);
+ ptr = strtok(NULL, " "); /* read the second node */
+ VALID_PTR_OR_EXIT(ptr, 7);
+ (*S)[K++] = atoi(ptr);
+ }
+ if (K > 0)
+ *S = realloc(*S, K * sizeof(unsigned int));
+ return K;
+}
+
+/*
+ * Read a file in ij format
+ */
+int read_ij(FILE *filein, unsigned int **I, unsigned int **J){
+
+ unsigned int size, K;
+ char buff[256];
+ char *ptr;
+
+ size = 20;
+ K = 0;
+
+ *I = malloc(size * sizeof(unsigned int));
+ *J = malloc(size * sizeof(unsigned int));
+ while(fgets(buff, 256, filein)){
+ if (buff[0] == '#')
+ continue;
+ if (K == size){
+ size += 20;
+ *I = realloc(*I, size*sizeof(unsigned int));
+ *J = realloc(*J, size*sizeof(unsigned int));
+ }
+ ptr = strtok(buff, " "); /* read the first node */
+ VALID_PTR_OR_EXIT(ptr, 7);
+ (*I)[K] = atoi(ptr);
+ ptr = strtok(NULL, " "); /* read the second node */
+ VALID_PTR_OR_EXIT(ptr, 7);
+ (*J)[K] = atoi(ptr);
+ K += 1;
+ }
+ if (K > 0){
+ *I = realloc(*I, K * sizeof(unsigned int));
+ *J = realloc(*J, K * sizeof(unsigned int));
+ }
+ return K;
+}
+
+
+/*
+ * Read a file in ij format -- weighted graphs -- if the input file is
+ * unweighted (i.e., no weights are provided), all the edges are
+ * assumed to have weight equal to 1.0
+ */
+int read_ij_w(FILE *filein, unsigned int **I, unsigned int **J,
+ double **W){
+
+ unsigned int size, K;
+ char buff[256];
+ char *ptr;
+
+ size = 20;
+ K = 0;
+
+ *I = malloc(size * sizeof(unsigned int));
+ *J = malloc(size * sizeof(unsigned int));
+ *W = malloc(size * sizeof(double));
+ while(fgets(buff, 256, filein)){
+ if (buff[0] == '#')
+ continue;
+ if (K == size){
+ size += 20;
+ *I = realloc(*I, size*sizeof(unsigned int));
+ *J = realloc(*J, size*sizeof(unsigned int));
+ *W = realloc(*W, size*sizeof(double));
+ }
+ ptr = strtok(buff, " "); /* read the first node */
+ VALID_PTR_OR_EXIT(ptr, 7);
+ (*I)[K] = atoi(ptr);
+ ptr = strtok(NULL, " "); /* read the second node */
+ VALID_PTR_OR_EXIT(ptr, 7);
+ (*J)[K] = atoi(ptr);
+ ptr = strtok(NULL, " "); /* read the weight */
+ if (!ptr)
+ (*W)[K] = 1.0;
+ else
+ (*W)[K] = atof(ptr);
+ K += 1;
+ }
+ if (K > 0){
+ *I = realloc(*I, K * sizeof(unsigned int));
+ *J = realloc(*J, K * sizeof(unsigned int));
+ *W = realloc(*W, K * sizeof(double));
+ }
+ return K;
+}
+
+
+
+void read_slap(FILE *filein, unsigned int *K, unsigned int *N,
+ unsigned int **J_slap, unsigned int **r_slap){
+
+ unsigned int *I=NULL, *J=NULL;
+ unsigned int i, k;
+
+ k = read_ij(filein, &I, &J);
+ *K = 2 * k;
+ I = realloc(I, 2*k * sizeof(unsigned int));
+ J = realloc(J, 2*k * sizeof(unsigned int));
+ for (i=k; i<2*k; i ++){
+ I[i] = J[i-k];
+ J[i] = I[i-k];
+ }
+
+ *N = convert_ij2slap(I, J, 2*k, r_slap, J_slap);
+ free(I);
+ free(J);
+ return;
+}
+
+void read_slap_w(FILE *filein, unsigned int *K, unsigned int *N,
+ unsigned int **J_slap, unsigned int **r_slap, double **W_slap){
+
+ unsigned int *I=NULL, *J=NULL;
+ double *W=NULL;
+ unsigned int i, k;
+
+ k = read_ij_w(filein, &I, &J, &W);
+ *K = 2 * k;
+ if (*K > 0){
+ I = realloc(I, (*K) * sizeof(unsigned int));
+ J = realloc(J, (*K) * sizeof(unsigned int));
+ W = realloc(W, (*K) * sizeof(double));
+ }
+ for (i=k; i<2*k; i ++){
+ I[i] = J[i-k];
+ J[i] = I[i-k];
+ W[i] = W[i-k];
+ }
+
+ *N = convert_ij2slap_w(I, J, W, 2*k, r_slap, J_slap, W_slap);
+ free(I);
+ free(J);
+ free(W);
+ return;
+}
+
+/**
+ *
+ * Read an I-J (directed) edge list, and transform it in SLAP
+ * notation, where the members of J_slap will be the outgoing
+ * neighbours
+ *
+ */
+void read_slap_dir(FILE *filein, unsigned int *K, unsigned int *N,
+ unsigned int **J_slap, unsigned int **r_slap){
+
+ unsigned int *I=NULL, *J=NULL;
+ unsigned int k;
+
+ k = read_ij(filein, &I, &J);
+ *K = k;
+
+ *N = convert_ij2slap(I, J, k, r_slap, J_slap);
+ free(I);
+ free(J);
+ return;
+}
+
+/**
+ *
+ * Read an I-J (directed) edge list, and transform it in SLAP
+ * notation, where the members of J_slap will be the incoming
+ * neighbours
+ *
+ */
+void read_slap_dir_incoming(FILE *filein, unsigned int *K, unsigned int *N,
+ unsigned int **J_slap, unsigned int **r_slap){
+
+ unsigned int *I=NULL, *J=NULL;
+ unsigned int k;
+
+ k = read_ij(filein, &I, &J);
+ *K = k;
+
+ *N = convert_ij2slap(J, I, k, r_slap, J_slap);
+ free(I);
+ free(J);
+ return;
+}
+
+
+
+
+unsigned int find_max(unsigned int *v, unsigned int N){
+
+ unsigned int i, max;
+
+ max = v[0];
+ i = 0;
+ while(++i < N){
+ if (v[i] > max)
+ max = v[i];
+ }
+ return max;
+}
+
+
+int convert_ij2slap(unsigned int *I, unsigned int *J, unsigned int K,
+ unsigned int ** r_slap, unsigned int **J_slap){
+
+ unsigned int tmp, max;
+ unsigned int i, pos;
+ unsigned int *p;
+
+ if (K < 1){
+ return 0;
+ }
+
+ max = find_max(I, K) + 1;
+ tmp = find_max(J, K) + 1;
+ if (tmp > max){
+ max = tmp ;
+ }
+
+ *r_slap = malloc( (max+1) * sizeof(unsigned int));
+ p = malloc(max * sizeof(unsigned int));
+
+ *J_slap = malloc(K * sizeof(unsigned int));
+
+ memset(*r_slap, 0, (max+1) * sizeof(unsigned int));
+ for(i=0; i<max + 1; i++)
+ (*r_slap)[i] = 0;
+ memset(p, 0, max * sizeof(unsigned int));
+ (*r_slap)[0] = 0;
+ for(i=0; i<K; i++){
+ (*r_slap)[ I[i] + 1] += 1;
+ }
+ for(i=1; i<=max; i++){
+ (*r_slap)[i] += (*r_slap)[i-1];
+ }
+ for(i=0; i<K; i++){
+ pos = (*r_slap) [ I[i] ] + p[ I[i] ];
+ (*J_slap)[pos] = J[i];
+ p[ I[i] ] += 1;
+ }
+ free(p);
+ return max;
+}
+
+
+
+int convert_ij2slap_w(unsigned int *I, unsigned int *J, double *W, unsigned int K,
+ unsigned int ** r_slap, unsigned int **J_slap,
+ double **W_slap){
+
+ unsigned int tmp, max;
+ unsigned int i, pos;
+ unsigned int *p;
+
+ max = find_max(I, K) + 1;
+ tmp = find_max(J, K) + 1;
+ if (tmp > max){
+ max = tmp ;
+ }
+ if (K<1){
+ return 0;
+ }
+
+ *r_slap = malloc( (max+1) * sizeof(unsigned int));
+ p = malloc(max * sizeof(unsigned int));
+
+ *J_slap = malloc(K * sizeof(unsigned int));
+ *W_slap = malloc(K * sizeof(double));
+
+ memset(*r_slap, 0, (max+1) * sizeof(unsigned int));
+ for(i=0; i<max + 1; i++)
+ (*r_slap)[i] = 0;
+ memset(p, 0, max * sizeof(unsigned int));
+ (*r_slap)[0] = 0;
+ for(i=0; i<K; i++){
+ (*r_slap)[ I[i] + 1] += 1;
+ }
+ for(i=1; i<=max; i++){
+ (*r_slap)[i] += (*r_slap)[i-1];
+ }
+ for(i=0; i<K; i++){
+ pos = (*r_slap) [ I[i] ] + p[ I[i] ];
+ (*J_slap)[pos] = J[i];
+ (*W_slap)[pos] = W[i];
+ p[ I[i] ] += 1;
+ }
+ free(p);
+ return max;
+}
+
+
+int convert_ij2slap_N(unsigned int *I, unsigned int *J, unsigned int K,
+ unsigned int N, unsigned int ** r_slap,
+ unsigned int **J_slap){
+
+ unsigned int max;
+ unsigned int i, pos;
+ unsigned int *p;
+
+ max = N;
+
+ *r_slap = malloc( (max+1) * sizeof(unsigned int));
+ p = malloc(max * sizeof(unsigned int));
+
+ *J_slap = malloc(K * sizeof(unsigned int));
+
+ memset(*r_slap, 0, (max+1) * sizeof(unsigned int));
+ for(i=0; i<max + 1; i++)
+ (*r_slap)[i] = 0;
+ memset(p, 0, max * sizeof(unsigned int));
+ (*r_slap)[0] = 0;
+ for(i=0; i<K; i++){
+ (*r_slap)[ I[i] + 1] += 1;
+ }
+ for(i=1; i<=max; i++){
+ (*r_slap)[i] += (*r_slap)[i-1];
+ }
+ for(i=0; i<K; i++){
+ pos = (*r_slap) [ I[i] ] + p[ I[i] ];
+ (*J_slap)[pos] = J[i];
+ p[ I[i] ] += 1;
+ }
+ free(p);
+ return max;
+}
+
+
+
+/* RIVEDERE QUESTA FUNZIONE...... PASSARE UN FILE COME ARGOMENTO E
+ USARE fprintf */
+void dump_deg_distr(unsigned int *degs, double *p, int n){
+
+ int i;
+
+ for(i=0; i<n; i++){
+ printf("%d %2.6f\n", degs[i], p[i]);
+ }
+}
+
+
+
+/* RIVEDERE QUESTA FUNZIONE...... PASSARE UN FILE COME ARGOMENTO E
+ USARE fprintf */
+void dump_deg_seq(unsigned int *nodes, int N){
+
+ int i;
+ for(i=0; i<N; i++){
+ printf("%d: %d\n", i, nodes[i]);
+ }
+}
+
+
+FILE* openfile_or_exit(char *filename, char *mode, int exitcode){
+
+ FILE *fileout;
+ char error_str[256];
+
+ fileout = fopen(filename, mode);
+ if (!fileout){
+ sprintf(error_str, "Error opening file %s", filename);
+ perror(error_str);
+ exit(exitcode);
+ }
+ return fileout;
+}
+
+int compare_int(const void *x1, const void *x2){
+ return *((unsigned int*)x1) - *((unsigned int*)x2);
+}
+
+int compare_double(const void *elem1, const void *elem2){
+
+ double *l1, *l2;
+
+ l1 = (double*)elem1;
+ l2 = (double*)elem2;
+ return (*l1 < *l2 ? -1 : (*l1 > *l2 ? 1 : 0));
+}
+
+void print_int(void *e){
+
+ int d;
+
+ d = *((int*)e);
+ printf("%d ", d);
+}
+
+void print_double(void *e){
+
+ double d;
+
+ d = *((double*)e);
+ printf("%g ", d);
+}
+
+
+
+void write_edges(FILE *fileout, unsigned int *J_slap,
+ unsigned int *r_slap, unsigned int N){
+
+ unsigned int i, j;
+
+ for(i=0; i<N; i++){
+ for (j=r_slap[i]; j<r_slap[i+1]; j++){
+ if (J_slap[j] > i){
+ fprintf(fileout, "%d %d\n", i, J_slap[j]);
+ }
+ }
+ }
+}
+
+
+void write_edges_dir(FILE *fileout, unsigned int *J_slap,
+ unsigned int *r_slap, unsigned int N){
+
+ unsigned int i, j;
+
+ for(i=0; i<N; i++){
+ for (j=r_slap[i]; j<r_slap[i+1]; j++){
+ fprintf(fileout, "%d %d\n", i, J_slap[j]);
+ }
+ }
+}
+
+
+
+
+/* Check if j is a neighbour of i */
+int is_neigh(unsigned int *J_slap, unsigned int *r_slap, unsigned int N,
+ unsigned int i, unsigned int j){
+
+ unsigned int l;
+ unsigned int count;
+ count = 0;
+ if (i >=N || j >=N)
+ return 0;
+ for(l=r_slap[i]; l<r_slap[i+1]; l++){
+ if (J_slap[l] == j)
+ count ++;
+ }
+ return count;
+}
+
+
+/* Check if j is a neighbour of i, using bsearch.
+
+ BE CAREFUL!!!! THIS WORKS ONLY IF THE LIST OF NEIGHBOURS HAS BEEN
+ PREVIOUSLY SORTED APPROPRIATELY, E.G. BY CALLING
+ sort_neighbours()
+
+*/
+int is_neigh_bs(unsigned int *J_slap, unsigned int *r_slap, unsigned int N,
+ unsigned int i, unsigned int j){
+
+ unsigned int *ptr;
+
+ ptr = bsearch(&j, & (J_slap[r_slap[i]]), r_slap[i+1] - r_slap[i], sizeof(unsigned int),
+ compare_int);
+ return (ptr == NULL ? 0: 1);
+}
+
+int find_neigh_in_Jslap(unsigned int *J_slap, unsigned int *r_slap, unsigned int N,
+ unsigned int i, unsigned int j, unsigned int *ret){
+
+ unsigned int *ptr;
+
+ ptr = bsearch(&j, & (J_slap[r_slap[i]]), r_slap[i+1] - r_slap[i], sizeof(unsigned int),
+ compare_int);
+ if (ptr == NULL){
+ return 0;
+ }
+ else{
+ *ret = (ptr - J_slap);
+ return 1;
+ }
+}
+
+
+double get_neigh_weight(unsigned int *J_slap, unsigned int *r_slap, double *W_slap,
+ unsigned int N, unsigned int i, unsigned int j){
+
+ unsigned int l;
+ double w = 0.0;
+
+ for(l=r_slap[i]; l<r_slap[i+1]; l++){
+ if (J_slap[l] == j)
+ w += W_slap[l];
+ }
+ return w;
+}
+
+
+
+
+
+void sort_neighbours(unsigned int *J_slap, unsigned int *r_slap, unsigned int N){
+
+ unsigned int i, *base;
+
+ for(i=0; i<N; i++){
+ base = J_slap + r_slap[i];
+ qsort(base, r_slap[i+1] - r_slap[i], sizeof(unsigned int), compare_int);
+ }
+}
+
+double strength(unsigned int *r_slap, double *W_slap, int i){
+
+ double s = 0;
+ int j;
+
+ for(j = r_slap[i]; j<r_slap[i+1]; j++){
+ s += W_slap[j];
+ }
+ return s;
+
+}
+
+
+void convert_slap2ij(unsigned int *J_slap, unsigned int *r_slap, int N, unsigned int *I, unsigned int *J){
+
+ int i, j, num;
+
+ num = 0;
+ for(i=0; i<N; i++){
+ for(j=r_slap[i]; j< r_slap[i+1]; j++){
+ I[num] = i;
+ J[num] = J_slap[j];
+ num += 1;
+ }
+ }
+}
+
+void show_progress(FILE *fout, char *s, unsigned int progress, unsigned int total){
+
+ char str[21]; /* 20 spaces */
+ double frac;
+ int num_char, i;
+
+ if (total){
+ frac = 1.0*progress/total;
+ }
+ else{
+ frac = 0.0;
+ }
+
+ num_char = (int)(frac * 20) - 1;
+ i = 20;
+ while(--i >= 0){
+ if (i > num_char)
+ str[i] = ' ';
+ else
+ str[i] = '.';
+ }
+ str[20] = '\0';
+ fprintf(fout, "\r%s [%s] %3d%%\r", s, str, (int)(frac * 100));
+}
+
+
+void shuffle_vector(unsigned int *v, unsigned int N){
+
+ int i, pos;
+
+ for(i=N-1; i>=0; i--){
+ pos = rand() % N;
+ if (pos != i){
+ v[i] ^= v[pos];
+ v[pos] ^= v[i];
+ v[i] ^= v[pos];
+ }
+ }
+}
+
+
+unsigned int read_partition(FILE *fin, unsigned int N, unsigned int *part){
+
+ unsigned int i;
+ char *ptr;
+ char buff[256];
+ unsigned int max_part = 0, val;
+
+
+ while(fgets(buff, 256, fin)){
+ if (buff[0] == '#')
+ continue;
+ ptr = strtok(buff, " "); /* read the node */
+ VALID_PTR_OR_EXIT(ptr, 7);
+ i = atoi(ptr);
+ if(i >= N){
+ fprintf(stderr, "Index %d out of bounds (0, %d) in read_partition (%s: %d)\n",
+ i, N, __FILE__, __LINE__);
+ }
+ ptr = strtok(NULL, " "); /* read the partition number */
+ VALID_PTR_OR_EXIT(ptr, 7);
+ val = atoi(ptr);
+ if (val > max_part){
+ max_part = val;
+ }
+ part[i] = val;
+ }
+ return max_part;
+}
+
+int degree(unsigned int *r_slap, unsigned int i){
+
+ return r_slap[i+1] - r_slap[i];
+}
+
+int my_strcasecmp(const char *s1, const char *s2){
+
+ char *c1, *c2;
+ int l1, l2;
+ int res, i;
+
+ l1 = strlen(s1);
+ l2 = strlen(s2);
+
+ c1 = malloc((1 + l1) * sizeof(char));
+ c2 = malloc((1 + l2) * sizeof(char));
+
+ for (i=0; i<l1; i++){
+ c1[i] = tolower(s1[i]);
+ }
+ c1[i] = '\0';
+
+ for (i=0; i<l2; i++){
+ c2[i] = tolower(s2[i]);
+ }
+ c2[i] = '\0';
+
+ res = strcmp(c1, c2);
+ free(c2);
+ free(c1);
+ return res;
+}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-19 15:15:47 +0000