1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
/**
* 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
*
*/
#ifndef __BST_PQ_H__
#define __BST_PQ_H__
#include "gen_stack.h"
/**
*
* This is an implementation of a Binary Search Tree augmented by a
* Priority Queue.
*
*/
#define PARENT(i) (int)(floor((i-1)/2))
#define MIN_QUEUE 0x01
#define MAX_QUEUE 0x02
typedef struct node{
unsigned int info; /* This is the ID of the neighbour used in the BST */
double key; /* This is the \DeltaQ values used as a key in the
PQ */
struct node* left; /* left child of the current element in the BST */
struct node* right; /* right child of the current element in the BST */
int index; /* Index of the current node in the PQ */
struct node *parent; /* Parent of the current node in the BST */
char active; /* indicates whether the node is active or not */
} node_t;
typedef struct{
void* (*alloc)();
void (*dealloc)(void*);
//void (*copy)(void *src, void *dst);
int (*compare)(unsigned int e1, unsigned int e2);
void (*print)(unsigned int, void*);
void *fileout;
} ilfunc_t;
typedef struct{
int (*compare)(double e1, double e2); /* compare two elements (standard comparator) */
void* (*alloc_vector)(unsigned int N); /* */
void (*dealloc_vector)(void *v); /* */
void* (*alloc_key)(void); /* Allocate an element for the key */
void (*copy_key)(void *src, void *dst); /* copy into key */
void (*print_elem)(void *e); /* print an element */
void (*set_key)(void *e, double k); /* set a new key to element e */
int (*compare_to_key)(void *e, double key); /* compare a key with the one of element e */
} gen_pqueue_func_t;
typedef struct {
node_t* root; /* root of the BST */
int N; /* Maximum size of the PQ */
int last; /* last element in the PQ */
node_t **v; /* vector of pointers to the nodes of the BST */
char qtype; /* type of PQ, either MIN_QUEUE or MAX_QUEUE */
ilfunc_t bst_funs;
gen_pqueue_func_t pq_funs;
gen_stack_t *node_cache; /* this is a pointer to a cache of
allocated nodes, implemented as a stack */
} bst_pq_struct_t;
typedef bst_pq_struct_t* bst_pq_t;
/* bst_pq interface */
/* init the BST_PQ */
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);
/* Destroy an existing BST_PQ */
void bst_pq_destroy(bst_pq_t b, char clear_cache);
/* lookup an element in the BST */
node_t* bst_pq_lookup(bst_pq_t b, unsigned int info);
/* insert a new element in the BST_PQ */
void bst_pq_insert(bst_pq_t b, unsigned int info, double key);
/* delete (or deactivate) an element in the BST_PQ */
int bst_pq_delete(bst_pq_t b, unsigned int info);
/* change the key of an element in the BST_PQ */
int bst_pq_change_key(bst_pq_t b, unsigned int info, double key);
/* return the head of the PQ */
void* bst_pq_peek(bst_pq_t);
/* Read the key of a given node of the BST */
double bst_pq_get_key(bst_pq_t b, unsigned int info);
/* 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);
/* Dump the BST */
void bst_pq_dump_bst(bst_pq_t b);
/* Show the PQ */
void bst_pq_dump_pq(bst_pq_t b);
/* See if a node is in the BST, either active or inactive */
node_t* bst_pq_lookup(bst_pq_t b, unsigned int info);
/* See if a node is in the BST and is ACTIVE */
node_t* bst_pq_lookup_active(bst_pq_t b, unsigned int info);
/* Insert a pre-allocated node_t in the BST_PQ */
//void bst_pq_insert_existing(bst_pq_t b, node_t *n);
#endif /*__BST_PQ_H__*/
|
