From 3aee2fd43e3059a699af2b63c6f2395e5a55e515 Mon Sep 17 00:00:00 2001 From: KatolaZ Date: Wed, 27 Sep 2017 15:06:31 +0100 Subject: First commit on github -- NetBunch 1.0 --- src/include/cum_distr.h | 60 +++++++++++++++++++ src/include/dset.h | 65 +++++++++++++++++++++ src/include/gen_heap.h | 84 +++++++++++++++++++++++++++ src/include/gen_pqueue.h | 108 ++++++++++++++++++++++++++++++++++ src/include/gen_stack.h | 54 +++++++++++++++++ src/include/iltree.h | 93 +++++++++++++++++++++++++++++ src/include/iltree_double.h | 62 ++++++++++++++++++++ src/include/utils.h | 138 ++++++++++++++++++++++++++++++++++++++++++++ 8 files changed, 664 insertions(+) create mode 100644 src/include/cum_distr.h create mode 100644 src/include/dset.h create mode 100644 src/include/gen_heap.h create mode 100644 src/include/gen_pqueue.h create mode 100644 src/include/gen_stack.h create mode 100644 src/include/iltree.h create mode 100644 src/include/iltree_double.h create mode 100644 src/include/utils.h (limited to 'src/include') diff --git a/src/include/cum_distr.h b/src/include/cum_distr.h new file mode 100644 index 0000000..a06336a --- /dev/null +++ b/src/include/cum_distr.h @@ -0,0 +1,60 @@ +/** + * 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 + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * 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 + * + *********************************************************************** + */ + +#ifndef __CUM_DISTR_H__ +#define __CUM_DISTR_H__ + +typedef struct{ + unsigned int id; + long double value; +} idval_t; + +typedef struct{ + unsigned int N; + unsigned int num; + idval_t *v; + long double sum; +} cum_distr_t; + +cum_distr_t* cum_distr_init(unsigned int N); + +int cum_distr_add(cum_distr_t *d, unsigned int id, long double val); + +unsigned int cum_distr_sample(cum_distr_t *d); + +void cum_distr_dump(cum_distr_t *d); + + +void cum_distr_destroy(cum_distr_t *d); + + +#endif //__CUM_DISTR_H__ diff --git a/src/include/dset.h b/src/include/dset.h new file mode 100644 index 0000000..0a072e5 --- /dev/null +++ b/src/include/dset.h @@ -0,0 +1,65 @@ +/** + * 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 + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * 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 + * + *********************************************************************** + */ + +#ifndef __DSET_H__ +#define __DSET_H__ + + +typedef struct dset{ + int rank; + struct dset *parent; + int id; +} dset_elem_t; + +typedef dset_elem_t* dset_t; + +void dset_makeset(dset_t *ds); + +void dset_destroy(dset_t ds); + +dset_t dset_find(dset_t ds); + +void dset_union(dset_t s1, dset_t s2); + +void dset_union_opt(dset_t d1, dset_t s2); + +dset_t dset_find_opt(dset_t ds); + +void dset_makeset_id(dset_t *ds, int id); + +int dset_find_id(dset_t ds); + +int dset_find_id_opt(dset_t ds); + + + +#endif /* __DSET_H__ */ diff --git a/src/include/gen_heap.h b/src/include/gen_heap.h new file mode 100644 index 0000000..0d434bc --- /dev/null +++ b/src/include/gen_heap.h @@ -0,0 +1,84 @@ +/** + * 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 + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * 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 + * + *********************************************************************** + */ + + +#ifndef __GEN_HEAP__ +#define __GEN_HEAP__ + + +#define MAX_HEAP 0x01 +#define MIN_HEAP 0x02 + +#define SORT_ASC 0x04 +#define SORT_DESC 0x08 + +#define ERR_DELETE -0x04 + +typedef struct{ + int (*compare)(const void *e1, const void *e2); + void* (*alloc_vector)(unsigned int N); + void (*dealloc_vector)(void *v); + void (*dealloc_elem)(void *e); + void (*print_elem)(void *e); +} gen_heap_func_t; + + +typedef struct{ + int N; + int last; + void **v; + gen_heap_func_t funs; + char htype; +} gen_heap_t; + + +#define PARENT(i) (int)(floor((i-1)/2)) + +gen_heap_t * gen_heap_init(unsigned int N, char htype, gen_heap_func_t *funs); + +void gen_heap_insert(gen_heap_t *h, void *elem); + +int gen_heap_delete(gen_heap_t *h, void **val); + +void* gen_heap_peek(gen_heap_t *h); + +gen_heap_t* gen_heap_from_array(void **v, unsigned int N, unsigned int last, char htype, + gen_heap_func_t *funs); + +void gen_heap_dump(gen_heap_t *h); + +void gen_heap_destroy(gen_heap_t *h); + +int gen_heap_sort(void *v, unsigned int N, size_t size, + char dir, int (*compar)(const void*, const void*)); + +#endif // __GEN_HEAP__ diff --git a/src/include/gen_pqueue.h b/src/include/gen_pqueue.h new file mode 100644 index 0000000..4dec23b --- /dev/null +++ b/src/include/gen_pqueue.h @@ -0,0 +1,108 @@ +/** + * 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 + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * 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 + * + *********************************************************************** + */ + + +#ifndef __GEN_PQUEUE_H__ +#define __GEN_PQUEUE_H__ + +#include "gen_heap.h" + +#define KEY_ERROR -1 +#define ID_ERROR -2 + +/* + * + * This implementation of the priority queue is based on gen_heap, but + * requires some additional code to work, since we need to maintain an + * array of "handles", i.e. a mapping between elements and their + * current positions in the heap + * + */ + +typedef struct{ + int (*compare)(const void *e1, const void *e2); /* compare two elements (standard comparator) */ + void* (*alloc_vector)(unsigned int N); /* */ + void (*dealloc_vector)(void *v); /* */ + void (*dealloc_elem)(void *e); /* deallocate an element */ + void (*print_elem)(void *e); /* print an element */ + int (*get_id)(void *e); /* get the id associated to an element + (used for handles management) */ + void* (*get_key)(void *e);/* get the current key of element e */ + void (*set_key)(void *e, void *k); /* set a new key to element e */ + int (*compare_to_key)(void *e, void *key); /* compare a key with the one of element e */ +} gen_pqueue_func_t; + + + +typedef struct{ + int N; + int last; + void **v; + gen_pqueue_func_t funs; + char qtype; + int *handles; +} gen_pqueue_t; + + + +#define MIN_QUEUE 0x01 +#define MAX_QUEUE 0x02 + + + +gen_pqueue_t * gen_pqueue_init(unsigned int N, char htype, gen_pqueue_func_t *funs); + +void gen_pqueue_insert(gen_pqueue_t *h, void *elem); + +int gen_pqueue_delete(gen_pqueue_t *h, void **val); + +void* gen_pqueue_peek(gen_pqueue_t *h); + +gen_pqueue_t* gen_pqueue_from_array(void **v, unsigned int N, unsigned int last, char htype, + gen_pqueue_func_t *funs); + +int gen_pqueue_change_key(gen_pqueue_t *q, unsigned int i, void *key); + +int gen_pqueue_force_key(gen_pqueue_t *q, unsigned int idx, void *key); + +void gen_pqueue_dump(gen_pqueue_t *h); + +void gen_pqueue_destroy(gen_pqueue_t *h); + +int gen_pqueue_get_handle(gen_pqueue_t *q, int id); + +void* gen_pqueue_get_key(gen_pqueue_t *q, int idx); + + + + +#endif // __GEN_PQUEUE_H__ diff --git a/src/include/gen_stack.h b/src/include/gen_stack.h new file mode 100644 index 0000000..2dc46c5 --- /dev/null +++ b/src/include/gen_stack.h @@ -0,0 +1,54 @@ +/** + * 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 + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * 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: + * + *********************************************************************** + */ + +#ifndef __GEN_STACK_H__ +#define __GEN_STACK_H__ + +typedef struct{ + unsigned int size; + int head; + void **v; +} gen_stack_t; + + +void gen_stack_create(gen_stack_t *s); + +void gen_stack_push(gen_stack_t *s, void *elem); + +int gen_stack_pop(gen_stack_t *s, void **res); + +int gen_stack_empty(gen_stack_t *s); + +int gen_stack_size(gen_stack_t *s); + + +#endif //__GEN_STACK_H__ diff --git a/src/include/iltree.h b/src/include/iltree.h new file mode 100644 index 0000000..d30dc83 --- /dev/null +++ b/src/include/iltree.h @@ -0,0 +1,93 @@ +/** + * 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 + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * 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 + * + *********************************************************************** + */ + +#ifndef __ILTREE_H__ +#define __ILTREE_H__ + + +typedef struct node{ + void* info; + struct node* left; + struct node* right; +} node_t; + +typedef struct{ + void* (*alloc)(); + void (*dealloc)(void*); + void (*copy)(void *src, void *dst); + int (*compare)(void*, void*); + void (*print)(void*, void*); + void *fileout; +} ilfunc_t; + + +typedef struct { + node_t* root; + ilfunc_t funs; +} iltree_struct_t; + + + +typedef iltree_struct_t* iltree_t; + + +void iltree_set_funs(iltree_t, ilfunc_t *); + +void iltree_destroy(iltree_t); + +void iltree_empty(iltree_t); + +void iltree_insert(iltree_t, void*); + +void* iltree_lookup(iltree_t, void*); + +void iltree_view_pre(iltree_t); + +iltree_t iltree_create(iltree_t); + +void iltree_empty_cache(iltree_t); + +void iltree_map(iltree_t, void (*func)(void*)); + +void iltree_map_args(iltree_t, void (*func)(void*, void*), void*); + +void* iltree_get_fileout(iltree_t t); + +void iltree_set_fileout(iltree_t t, void *f); + +void* iltree_getmin(iltree_t t); + +void* iltree_getmax(iltree_t t); + + + +#endif /* __ILTREE_H__*/ diff --git a/src/include/iltree_double.h b/src/include/iltree_double.h new file mode 100644 index 0000000..f294aae --- /dev/null +++ b/src/include/iltree_double.h @@ -0,0 +1,62 @@ +/** + * 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 + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * 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" + * + */ + +#ifndef __ILTREE_DOUBLE_H__ +#define __ILTREE_DOUBLE_H__ + + + +#include "iltree.h" + +iltree_t iltree_double_init(iltree_t t, void *fileout); + + +void* alloc_double(); + +void dealloc_double(void *elem); + +void copy_double(void *elem1, void *elem2); + +int compare_long_double(void *elem1, void *elem2); + +void print_long_double(void *elem, void *fileout); + + + +void iltree_double_dump_edges(iltree_t t); + + +#endif // __ILTREE_DOUBLE_H__ diff --git a/src/include/utils.h b/src/include/utils.h new file mode 100644 index 0000000..599a287 --- /dev/null +++ b/src/include/utils.h @@ -0,0 +1,138 @@ +/** + * 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 + * . + * + * (c) Vincenzo Nicosia 2009-2017 -- + * + * 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 + * + *********************************************************************** + */ + +#ifndef __UTILS_H__ +#define __UTILS_H__ + +#define VALID_PTR_OR_EXIT(ptr, status) \ + if (!ptr){\ + fprintf(stderr, "Error in %s at line %d -- Exiting!!!\n", \ + __FILE__, __LINE__);\ + exit(status);\ + } + + +int read_deg_distr(FILE *filein, unsigned int **degs, unsigned int **Nk, double **p); + +int read_deg_seq(FILE *filein, unsigned int **nodes); + +int read_stubs(FILE *filein, unsigned int **S); + +int read_ij(FILE *filein, unsigned int **i, unsigned int **j); + +int read_ij_w(FILE *filein, unsigned int **i, unsigned int **j, double **w); + +void read_slap(FILE *filein, unsigned int *K, unsigned int *N, + unsigned int **J_slap, unsigned int **r_slap); + +void read_slap_w(FILE *filein, unsigned int *K, unsigned int *N, + unsigned int **J_slap, unsigned int **r_slap, double **W_slap); + +void read_slap_dir(FILE *filein, unsigned int *K, unsigned int *N, + unsigned int **J_slap, unsigned int **r_slap); + +void read_slap_dir_incoming(FILE *filein, unsigned int *K, unsigned int *N, + unsigned int **J_slap, unsigned int **r_slap); + + +int convert_ij2slap(unsigned int *I, unsigned int *J, unsigned int K, + unsigned int ** r_slap, unsigned int **J_slap); + +int convert_ij2slap_N(unsigned int *I, unsigned int *J, unsigned int K, + unsigned int N, unsigned int ** r_slap, + unsigned int **J_slap); + +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); + + +void write_edges(FILE *fileout, unsigned int *J_slap, + unsigned int *r_slap, unsigned int N); + +void write_edges_dir(FILE *fileout, unsigned int *J_slap, + unsigned int *r_slap, unsigned int N); + + +void dump_deg_distr(unsigned int *degs, double *p, int n); + +void dump_deg_seq(unsigned int *nodes, int N); + + +FILE* openfile_or_exit(char *filename, char *mode, int exitcode); + +int compare_int(const void *x1, const void *x2); + +int compare_double(const void *x1, const void *x2); + +void print_int(void *elem); + +void print_double(void *elem); + +unsigned int find_max(unsigned int *, unsigned int); + +int is_neigh(unsigned int *J_slap, unsigned int *r_slap, unsigned int N, + unsigned int i, unsigned int j); + +int is_neigh_bs(unsigned int *J_slap, unsigned int *r_slap, unsigned int N, + unsigned int i, unsigned int j); + +double get_neigh_weight(unsigned int *J_slap, unsigned int *r_slap, double *W_slap, + unsigned int N, unsigned int i, unsigned int j); + +/* sort the adjacency list of neighbours of each node in ascending order */ +void sort_neighbours(unsigned int *J_slap, unsigned int *r_slap, unsigned int N); + +double strength(unsigned int *r_slap, double *W_slap, int i); + +void convert_slap2ij(unsigned int *J_slap, unsigned int *r_slap, int N, unsigned int *I, unsigned int *J); + +/* Show a simple progress message */ +void show_progress(FILE *fout, char *s, unsigned int progress, unsigned int total); + + +/* find the position of a neghbour of i (node j) in J_slap */ +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); + + +/* shuffle a vector of integers in-place */ +void shuffle_vector(unsigned int *v, unsigned int N); + + +unsigned int read_partition(FILE *fin, unsigned int N, unsigned int *part); + +int degree (unsigned int *r_slap, unsigned int i); + +int my_strcasecmp(const char *s1, const char *s2); + +#endif /*__UTILS_H__*/ -- cgit v1.2.3