summaryrefslogtreecommitdiff
path: root/src/cnm/bst_pq.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/cnm/bst_pq.c')
-rw-r--r--src/cnm/bst_pq.c808
1 files changed, 808 insertions, 0 deletions
diff --git a/src/cnm/bst_pq.c b/src/cnm/bst_pq.c
new file mode 100644
index 0000000..9502f4e
--- /dev/null
+++ b/src/cnm/bst_pq.c
@@ -0,0 +1,808 @@
+/**
+ * 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 Binary Search Tree augmented by a
+ * Priority Queue. This data structure is central to the
+ * implementation of the Clauset-Newman-Moore greedy modularity
+ * optimisation algorithm
+ *
+ */
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <assert.h>
+
+#include "utils.h"
+#include "bst_pq.h"
+
+
+
+/* BST-related functions */
+
+
+void __recursive_preorder(node_t *cur, ilfunc_t *funs){
+
+ if(cur->left){
+ __recursive_preorder(cur->left, funs);
+ }
+ if(cur -> active)
+ 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);
+ cur->left = NULL;
+ }
+ if(cur->right){
+ __recursive_destroy(cur->right, funs);
+ cur->right = NULL;
+ }
+}
+
+
+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); */
+ assert(res != 0);
+ if ( res > 0){
+ if (cur->left){
+ return __recursive_insert(cur->left, elem, f);
+ }
+ else{
+ cur->left = elem;
+ elem->parent = cur;
+ return 0;
+ }
+ }
+ else if (res < 0){
+ if (cur->right){
+ return __recursive_insert(cur->right, elem, f);
+ }
+ else{
+ cur->right = elem;
+ elem->parent = cur;
+ return 0;
+ }
+ }
+ if (cur -> active){
+ printf("warning!!!!! duplicate entry!!!!!!\n\n");
+ exit(1);
+ }
+ else
+ cur->active = 1;
+ return -1;
+}
+
+
+
+void* __recursive_lookup(node_t *cur, int 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{ /* res == 0, we found the element we were looking for */
+ return cur;
+ }
+}
+
+
+
+node_t* __recursive_getmin(node_t *cur){
+
+ if(cur->left){
+ return __recursive_getmin(cur->left);
+ }
+ else{
+ return cur;
+ }
+
+}
+
+
+node_t* __tree_getmin(node_t *n){
+
+ if (!n){
+ return NULL;
+ }
+ else{
+ return __recursive_getmin(n);
+ }
+
+}
+
+
+/* This is used by __tree__delete to put another tree v in place of
+ the current node u */
+
+
+void __tree_transplant(bst_pq_t t, node_t *u, node_t * v){
+
+ if (u->parent == NULL){
+ t->root = v;
+ }
+ else if(u == u->parent->left){
+ u->parent->left = v;
+ }
+ else{
+ u->parent->right = v;
+ }
+ if (v != NULL){
+ v->parent = u->parent;
+ }
+
+}
+
+
+void __tree_delete(bst_pq_t t, node_t *z){
+
+ node_t *y;
+
+ if (z == NULL)
+ return;
+
+ if (z->left == NULL){
+ __tree_transplant(t, z, z->right);
+ }
+ else if(z->right == NULL){
+ __tree_transplant(t, z, z->left);
+ }
+ else{
+ y = __tree_getmin(z->right);
+ if (y->parent != z){
+ __tree_transplant(t, y, y->right);
+ y->right = z->right;
+ y->right->parent = y;
+ }
+ __tree_transplant(t, z, y);
+ y->left = z->left;
+ y->left->parent = y;
+ }
+}
+
+
+
+
+void bst_pq_tree_destroy(bst_pq_t t){
+
+ if(t->root)
+ __recursive_destroy(t->root, & (t->bst_funs));
+ free(t);
+}
+
+
+
+
+void __bst_pq_tree_view_pre(bst_pq_t t){
+
+ if (t->root){
+ printf("----\n");
+ __recursive_preorder(t->root, & (t->bst_funs));
+ printf("\n----\n");
+ }
+ else
+ printf("----- Empty tree!!!! -----\n");
+
+}
+
+
+
+void* __bst_pq_tree_lookup(bst_pq_t t , int elem){
+
+ if(t->root)
+ return __recursive_lookup(t->root, elem, & (t->bst_funs) );
+ else
+ return NULL;
+}
+
+
+
+
+
+/* void bst_pq_tree_map(bst_pq_t t, void (*func)(void*)){ */
+
+/* __recursive_map(t->root, func); */
+
+/* } */
+
+
+/* void bst_pq_tree_map_args(bst_pq_t t, void (*func)(void*, void*), void *args){ */
+
+/* __recursive_map_args(t->root, func, args); */
+
+/* } */
+
+void* bst_pq_tree_get_fileout(bst_pq_t t){
+
+ return t->bst_funs.fileout;
+}
+
+void bst_pq_tree_set_fileout(bst_pq_t t, void *f){
+
+ t->bst_funs.fileout = f;
+}
+
+
+
+node_t* __recursive_getmax(node_t *cur){
+
+ if(cur->right){
+ return __recursive_getmax(cur->right);
+ }
+ else{
+ return cur;
+ }
+
+}
+
+
+void* bst_pq_tree_getmax(bst_pq_t t){
+
+ if (!t){
+ return NULL;
+ }
+ else{
+ return __recursive_getmax(t->root);
+ }
+
+}
+
+
+/************************
+ * PQ-related functions *
+ ************************/
+
+void __update_handle(bst_pq_t q, int idx){
+
+ node_t *n;
+ n = (node_t*) q->v[idx];
+ n->index = idx;
+ //q->handles[q->pq_funs.get_id(q->v[idx])] = idx;
+}
+
+
+
+void __bst_pq_queue_sift_up(bst_pq_t q, int i){
+
+ int idx, parent;
+ void *tmp;
+
+ if ( q->last < 0)
+ return; /* no sifting if the PQ is empty!!! */
+
+ idx = i;
+ parent = PARENT(idx);
+
+ switch(q->qtype){
+ case MAX_QUEUE:
+ while ( idx >0 && q->pq_funs.compare(q->v[idx]->key, q->v[parent]->key) > 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-> pq_funs.compare(q->v[idx]->key, q->v[parent]->key) < 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 __bst_pq_queue_sift_down(bst_pq_t q, int i){
+
+ int left, right, largest, smallest;
+ void *tmp;
+
+ if ( q->last < 0)
+ return; /* no sifting if the PQ is empty!!! */
+ if( i > q->last)
+ return; /* no sifting if the index i is beyond the end of the PQ */
+
+ switch(q->qtype){
+ case MAX_QUEUE:
+ largest = i;
+ left = 2 * i + 1;
+ right = 2 * i + 2;
+
+ if (left <= q->last && q->pq_funs.compare(q->v[left]->key, q->v[largest]->key) > 0){
+ largest = left;
+ }
+ if (right <= q->last && q->pq_funs.compare(q->v[right]->key, q->v[largest]->key) > 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);
+ __bst_pq_queue_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->pq_funs.compare(q->v[left]->key, q->v[smallest]->key) < 0){
+ smallest = left;
+ }
+ if (right <= q->last && q->pq_funs.compare(q->v[right]->key, q->v[smallest]->key) < 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);
+ __bst_pq_queue_sift_down(q, smallest);
+ }
+ else{
+ __update_handle(q, i);
+ }
+ break;
+ }
+}
+
+
+void __bst_pq_queue_insert(bst_pq_t q, void *elem){
+
+ //void *tmp;
+
+ if (q->last == q->N-1){
+ /* reallocate the array to arrange a few new elements */
+ q->N += 10;
+ q->v = realloc(q->v, (q->N) * sizeof(void*));
+ VALID_PTR_OR_EXIT(q->v, 17);
+ //q->v = tmp;
+ }
+
+ q->last += 1;
+ q->v[q->last] = elem;
+ __update_handle(q, q->last);
+ __bst_pq_queue_sift_up(q, q->last);
+
+}
+
+
+
+int __bst_pq_queue_delete_index(bst_pq_t q, int index){
+
+ if (q->last >=0 && index <= q->last){
+ //*val = q->v[0];
+ q->v[index] = q->v[q->last];
+ q->last -= 1;
+ __bst_pq_queue_sift_down(q, index);
+ return 0;
+ }
+ else{
+ return 1;
+ }
+}
+
+
+
+void* __bst_pq_queue_peek(bst_pq_t q){
+
+ if (q->last >= 0)
+ return q->v[0];
+ else
+ return NULL;
+}
+
+
+
+int __bst_pq_queue_force_key(bst_pq_t q, unsigned int idx, double key){
+
+ switch(q->qtype){
+ case MAX_QUEUE:
+ if (q->pq_funs.compare_to_key(q->v[idx], key) > 0){
+ //q->pq_funs.set_key(q->v[idx], key);
+ q->v[idx]->key = key;
+ __bst_pq_queue_sift_down(q, idx);
+ }
+ else{
+ //q->pq_funs.set_key(q->v[idx], key);
+ q->v[idx]->key = key;
+ __bst_pq_queue_sift_up(q, idx);
+ }
+ break;
+ case MIN_QUEUE:
+ if (q->pq_funs.compare_to_key(q->v[idx], key) < 0){
+ //q->pq_funs.set_key(q->v[idx], key);
+ q->v[idx]->key = key;
+ __bst_pq_queue_sift_down(q, idx);
+ }
+ else{
+ //q->pq_funs.set_key(q->v[idx], key);
+ q->v[idx]->key = key;
+ __bst_pq_queue_sift_up(q, idx);
+ }
+ break;
+ }
+ return 0;
+}
+
+
+
+void __bst_pq_queue_dump(bst_pq_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->pq_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->pq_funs.print_elem(q->v[i]);
+ printf(" (");
+ q->pq_funs.print_elem(q->v[2*i+1]);
+ printf(", ");
+ q->pq_funs.print_elem(q->v[2*i+2]);
+ printf(")\n");
+ }
+ else{
+ printf("%d: ", i);
+ q->pq_funs.print_elem(q->v[i]);
+ printf(" (");
+ q->pq_funs.print_elem(q->v[2*i+1]);
+ printf(", NULL)\n");
+ }
+ else{
+ printf("%d: ", i);
+ q->pq_funs.print_elem(q->v[i]);
+ printf(" (NULL, NULL)\n");
+ }
+ }
+ else{
+ printf("%d: ", i);
+ q->pq_funs.print_elem(q->v[i]);
+ printf(" (NULL, NULL)\n");
+ }
+ }
+ printf("\n");
+}
+
+
+
+
+/* bst_pq interface */
+
+/* init the BST_PQ -- TESTED --*/
+
+bst_pq_t bst_pq_create(ilfunc_t *bst_funs, gen_pqueue_func_t *pq_funs, char qtype,
+ unsigned int N, gen_stack_t *node_cache){
+
+ bst_pq_t b;
+
+ b = (bst_pq_t)malloc(sizeof(bst_pq_struct_t));
+ b->root = NULL;
+ b->bst_funs = *bst_funs;
+
+ b->bst_funs.fileout = stdout;
+ b->qtype = qtype;
+ b->N = N;
+ b->last = -1;
+ b->pq_funs = *pq_funs;
+ b->v = b->pq_funs.alloc_vector(N);
+ if (node_cache == NULL){
+ b->node_cache = malloc(sizeof(gen_stack_t));
+ gen_stack_create(b->node_cache);
+ }
+ else{
+ b->node_cache = node_cache;
+ }
+ return b;
+}
+
+
+
+
+
+
+
+/* insert a new element in the BST_PQ -- TESTED */
+void bst_pq_insert(bst_pq_t b, unsigned int elem_info, double elem_key){
+
+ /* insert the element in the tree first */
+ node_t *n;
+ int err;
+
+ n = __bst_pq_tree_lookup(b, elem_info);
+
+ /* The following assert should fail ONLY if there is an auto-loop */
+ assert(n == NULL);
+
+ if (gen_stack_empty(b->node_cache)){
+ n = (node_t*)malloc(sizeof(node_t));
+ //n->info = b->bst_funs.alloc();
+ //n->key = b->pq_funs.alloc_key();
+ }
+ else{
+ err = gen_stack_pop(b->node_cache, (void**) &n);
+ if (err){
+ n = malloc(sizeof(node_t));
+ //n->info = b->bst_funs.alloc();
+ //n->key = b->pq_funs.alloc_key();
+ }
+ }
+ //b->bst_funs.copy(elem_info, n->info);
+ n->info = elem_info;
+ n->left = n->right = NULL;
+ if (b->root == NULL){
+ b->root = n;
+ n->parent = NULL;
+ }
+ else{
+ err = __recursive_insert(b->root, n, & (b->bst_funs));
+ if(err){
+ fprintf(stderr, "Error during insert into BST!!! (%s: %d)\n",
+ __FILE__, __LINE__);
+ exit(23);
+ }
+ }
+ n->active = 1;
+ n->index = -1;
+ /* set the key as needed */
+ //b->pq_funs.copy_key(elem_key, n->key);
+ n->key = elem_key;
+
+ /* then, insert the pointer to the element in the PQ */
+ __bst_pq_queue_insert(b, n);
+
+}
+
+/* delete (or deactivate) the element associated to a given info -- TESTED --*/
+int bst_pq_delete(bst_pq_t b, unsigned int info){
+
+ node_t *n;
+
+ n = __bst_pq_tree_lookup(b, info);
+
+ if (n != NULL){
+ __tree_delete(b, n);
+ n->active = 0; /* deactivate the node */
+ /* After the node has been deleted from the tree, we add it to
+ the node cache */
+ gen_stack_push(b->node_cache, n);
+ __bst_pq_queue_delete_index(b, n->index); /* remove the reference form the PQ */
+ return 0; /* No problem */
+ }
+ return 1; /* the element does not exist */
+}
+
+/* change the key of an element in the BST_PQ -- TESTED --*/
+int bst_pq_change_key(bst_pq_t b, unsigned int info, double key){
+
+ node_t *n;
+ int idx;
+
+ n = __bst_pq_tree_lookup(b, info);
+ if (n != NULL){
+ /* the element exists. We should just force its key and sift as required */
+ idx = n->index;
+ __bst_pq_queue_force_key(b, idx, key);
+ return 0; /* No problem */
+ }
+ else{
+ return 1; /* The element does not exist */
+ }
+
+}
+
+/* return the head of the PQ -- TESTED --*/
+void* bst_pq_peek(bst_pq_t q){
+
+ return __bst_pq_queue_peek(q);
+}
+
+
+/* Read the key of a given node of the BST */
+double bst_pq_get_key(bst_pq_t b, unsigned int info){
+
+ node_t *n;
+
+ n = __bst_pq_tree_lookup(b, info);
+ if (n != NULL){
+ return n->key;
+ }
+ else{
+ return -100000;
+ }
+}
+
+
+/* Read the key of the element of index "index" in the PQ */
+double bst_pq_get_key_from_index(bst_pq_t b, int index){
+
+ node_t *n;
+
+ n = (node_t *)b->v[index];
+
+ return n->key;
+}
+
+
+/* Dump the BST -- TESTED -- */
+void bst_pq_dump_bst(bst_pq_t b){
+
+ __bst_pq_tree_view_pre(b);
+
+}
+
+/* Show the PQ -- TESTED -- */
+void bst_pq_dump_pq(bst_pq_t b){
+
+ __bst_pq_queue_dump(b);
+
+}
+
+/* Perform a lookup of an element in the BST_PQ -- TESTED-- */
+node_t* bst_pq_lookup(bst_pq_t b, unsigned int info){
+
+ return __bst_pq_tree_lookup(b, info);
+}
+
+
+node_t* bst_pq_lookup_active(bst_pq_t b, unsigned int info){
+
+ node_t *ptr;
+
+ ptr = __bst_pq_tree_lookup(b, info);
+
+ if(ptr)
+ assert(ptr->active != 0);
+
+ if (ptr != NULL && ptr->active){
+ return ptr;
+ }
+
+ return NULL;
+}
+
+
+/* void bst_pq_insert_existing(bst_pq_t b, node_t *n){ */
+
+/* /\* insert the element in the tree first *\/ */
+/* if (n == NULL){ */
+/* fprintf(stderr, "Error!!!! Attempt to insert a NULL existing element (%s: %d)\n", */
+/* __FILE__, __LINE__); */
+/* exit(37); */
+/* } */
+/* /\* n->info = b->bst_funs.alloc(); *\/ */
+/* /\* n->key = b->pq_funs.alloc_key(); *\/ */
+/* /\* b->bst_funs.copy(elem_info, n->info); *\/ */
+/* n->left = n->right = NULL; */
+/* if (b->root == NULL){ */
+/* b->root = n; */
+/* n->parent = NULL; */
+/* } */
+/* else{ */
+/* __recursive_insert(b->root, n, & (b->bst_funs)); */
+/* } */
+
+/* n->active = 1; */
+/* /\* set the key as needed *\/ */
+/* //b->pq_funs.copy_key(elem_key, n->key); */
+
+/* /\* then, insert the pointer to the element in the PQ *\/ */
+/* __bst_pq_queue_insert(b, n); */
+
+/* } */
+
+
+
+
+
+
+void bst_pq_destroy(bst_pq_t b, char destroy_cache){
+
+ int i;
+ node_t *n;
+
+ if (b == NULL)
+ return;
+
+ if(destroy_cache && b->node_cache != NULL ){
+ while(!gen_stack_pop(b->node_cache, (void**) &n)){
+ //b->bst_funs.dealloc(n->info);
+ //free(n->key);
+ free(n);
+ }
+ free(b->node_cache->v);
+ free(b->node_cache);
+ }
+
+ for(i=b->last; i>=0; i--){
+ __tree_delete(b, b->v[i]);
+ __bst_pq_queue_delete_index(b, i); /* remove the reference form the PQ */
+ //bst_pq_delete(b, b->v[i]->info);
+ //b->bst_funs.dealloc(b->v[i]->info);
+ //free(b->v[i]->key);
+ free(b->v[i]);
+ }
+ free(b->v);
+ free(b);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-03 15:30:14 +0000