File: igraph_types_internal.h

package info (click to toggle)
r-cran-igraph 0.7.1-1~bpo8%2B1
  • links: PTS, VCS
  • area: main
  • in suites: jessie-backports
  • size: 14,280 kB
  • sloc: ansic: 150,105; cpp: 19,404; fortran: 3,777; yacc: 1,164; tcl: 931; lex: 484; makefile: 13; sh: 9
file content (395 lines) | stat: -rw-r--r-- 15,076 bytes parent folder | download | duplicates (8)
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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
/* -*- mode: C -*-  */
/* 
   IGraph library.
   Copyright (C) 2009-2012  Gabor Csardi <csardi.gabor@gmail.com>
   334 Harvard street, Cambridge, MA 02139 USA
   
   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 2 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, write to the Free Software
   Foundation, Inc.,  51 Franklin Street, Fifth Floor, Boston, MA 
   02110-1301 USA

*/

#ifndef IGRAPH_TYPES_INTERNAL_H
#define IGRAPH_TYPES_INTERNAL_H

#undef __BEGIN_DECLS
#undef __END_DECLS
#ifdef __cplusplus
# define __BEGIN_DECLS extern "C" {
# define __END_DECLS }
#else
# define __BEGIN_DECLS /* empty */
# define __END_DECLS /* empty */
#endif

#include "igraph_types.h"
#include "igraph_matrix.h"
#include "igraph_stack.h"
#include "igraph_strvector.h"
#include "igraph_vector.h"
#include "igraph_vector_ptr.h"

__BEGIN_DECLS

/* -------------------------------------------------- */
/* Indexed heap                                       */
/* -------------------------------------------------- */

/**
 * Indexed heap data type.
 * \ingroup internal
 */

typedef struct s_indheap {
  igraph_real_t* stor_begin;
  igraph_real_t* stor_end;
  igraph_real_t* end;
  int destroy;
  long int* index_begin;
} igraph_indheap_t;

#define IGRAPH_INDHEAP_NULL { 0,0,0,0,0 }

int igraph_indheap_init           (igraph_indheap_t* h, long int size);
int igraph_indheap_init_array     (igraph_indheap_t *t, igraph_real_t* data, long int len);
void igraph_indheap_destroy        (igraph_indheap_t* h);
int igraph_indheap_clear(igraph_indheap_t *h);
igraph_bool_t igraph_indheap_empty          (igraph_indheap_t* h);
int igraph_indheap_push           (igraph_indheap_t* h, igraph_real_t elem);
int igraph_indheap_push_with_index(igraph_indheap_t* h, long int idx, igraph_real_t elem);
int igraph_indheap_modify(igraph_indheap_t* h, long int idx, igraph_real_t elem);
igraph_real_t igraph_indheap_max       (igraph_indheap_t* h);
igraph_real_t igraph_indheap_delete_max(igraph_indheap_t* h);
long int igraph_indheap_size      (igraph_indheap_t* h);
int igraph_indheap_reserve        (igraph_indheap_t* h, long int size);
long int igraph_indheap_max_index(igraph_indheap_t *h);

void igraph_indheap_i_build(igraph_indheap_t* h, long int head);
void igraph_indheap_i_shift_up(igraph_indheap_t* h, long int elem);
void igraph_indheap_i_sink(igraph_indheap_t* h, long int head);
void igraph_indheap_i_switch(igraph_indheap_t* h, long int e1, long int e2);

/* -------------------------------------------------- */
/* Doubly indexed heap                                */
/* -------------------------------------------------- */

/* This is a heap containing double elements and 
   two indices, its intended usage is the storage of
   weighted edges.
*/

/**
 * Doubly indexed heap data type.
 * \ingroup internal
 */

typedef struct s_indheap_d {
  igraph_real_t* stor_begin;
  igraph_real_t* stor_end;
  igraph_real_t* end;
  int destroy;
  long int* index_begin;
  long int* index2_begin;
} igraph_d_indheap_t;


#define IGRAPH_D_INDHEAP_NULL { 0,0,0,0,0,0 }

int igraph_d_indheap_init           (igraph_d_indheap_t* h, long int size);
void igraph_d_indheap_destroy        (igraph_d_indheap_t* h);
igraph_bool_t igraph_d_indheap_empty          (igraph_d_indheap_t* h);
int igraph_d_indheap_push           (igraph_d_indheap_t* h, igraph_real_t elem, 
			      long int idx, long int idx2);
igraph_real_t igraph_d_indheap_max       (igraph_d_indheap_t* h);
igraph_real_t igraph_d_indheap_delete_max(igraph_d_indheap_t* h);
long int igraph_d_indheap_size      (igraph_d_indheap_t* h);
int igraph_d_indheap_reserve        (igraph_d_indheap_t* h, long int size);
void igraph_d_indheap_max_index(igraph_d_indheap_t *h, long int *idx, long int *idx2);

void igraph_d_indheap_i_build(igraph_d_indheap_t* h, long int head);
void igraph_d_indheap_i_shift_up(igraph_d_indheap_t* h, long int elem);
void igraph_d_indheap_i_sink(igraph_d_indheap_t* h, long int head);
void igraph_d_indheap_i_switch(igraph_d_indheap_t* h, long int e1, long int e2);

/* -------------------------------------------------- */
/* Two-way indexed heap                               */
/* -------------------------------------------------- */

/* This is a smart indexed heap. In addition to the "normal" indexed heap
   it allows to access every element through its index in O(1) time. 
   In other words, for this heap the _modify operation is O(1), the 
   normal heap does this in O(n) time.... */

typedef struct igraph_2wheap_t {
  long int size;
  igraph_vector_t data;
  igraph_vector_long_t index;
  igraph_vector_long_t index2;
} igraph_2wheap_t;

int igraph_2wheap_init(igraph_2wheap_t *h, long int size);
void igraph_2wheap_destroy(igraph_2wheap_t *h);
int igraph_2wheap_clear(igraph_2wheap_t *h);
int igraph_2wheap_push_with_index(igraph_2wheap_t *h, 
				  long int idx, igraph_real_t elem);
igraph_bool_t igraph_2wheap_empty(const igraph_2wheap_t *h);
long int igraph_2wheap_size(const igraph_2wheap_t *h);
long int igraph_2wheap_max_size(const igraph_2wheap_t *h);
igraph_real_t igraph_2wheap_max(const igraph_2wheap_t *h);
long int igraph_2wheap_max_index(const igraph_2wheap_t *h);
igraph_real_t igraph_2wheap_deactivate_max(igraph_2wheap_t *h);
igraph_bool_t igraph_2wheap_has_elem(const igraph_2wheap_t *h, long int idx);
igraph_bool_t igraph_2wheap_has_active(const igraph_2wheap_t *h, long int idx);
igraph_real_t igraph_2wheap_get(const igraph_2wheap_t *h, long int idx);
igraph_real_t igraph_2wheap_delete_max(igraph_2wheap_t *h);
igraph_real_t igraph_2wheap_delete_max_index(igraph_2wheap_t *h, long int *idx);
int igraph_2wheap_modify(igraph_2wheap_t *h, long int idx, igraph_real_t elem);
int igraph_2wheap_check(igraph_2wheap_t *h);

/**
 * Trie data type
 * \ingroup internal
 */

typedef struct s_igraph_trie_node {
  igraph_strvector_t strs;
  igraph_vector_ptr_t children;
  igraph_vector_t values;
} igraph_trie_node_t;

typedef struct s_igraph_trie {
  igraph_strvector_t strs;
  igraph_vector_ptr_t children;
  igraph_vector_t values;
  long int maxvalue;
  igraph_bool_t storekeys;
  igraph_strvector_t keys;
} igraph_trie_t;

#define IGRAPH_TRIE_NULL { IGRAPH_STRVECTOR_NULL, IGRAPH_VECTOR_PTR_NULL, \
                           IGRAPH_VECTOR_NULL, 0, 0, IGRAPH_STRVECTOR_NULL }
#define IGRAPH_TRIE_INIT_FINALLY(tr, sk) \
  do { IGRAPH_CHECK(igraph_trie_init(tr, sk)); \
  IGRAPH_FINALLY(igraph_trie_destroy, tr); } while (0)

int igraph_trie_init(igraph_trie_t *t, igraph_bool_t storekeys);
void igraph_trie_destroy(igraph_trie_t *t);
int igraph_trie_get(igraph_trie_t *t, const char *key, long int *id);
int igraph_trie_check(igraph_trie_t *t, const char *key, long int *id);
int igraph_trie_get2(igraph_trie_t *t, const char *key, long int length, 
		     long int *id);
void igraph_trie_idx(igraph_trie_t *t, long int idx, char **str);
int igraph_trie_getkeys(igraph_trie_t *t, const igraph_strvector_t **strv);
long int igraph_trie_size(igraph_trie_t *t);

/**
 * 2d grid containing points
 */

typedef struct igraph_2dgrid_t {
  igraph_matrix_t *coords;
  igraph_real_t minx, maxx, deltax;
  igraph_real_t miny, maxy, deltay;
  long int stepsx, stepsy;
  igraph_matrix_t startidx;
  igraph_vector_t next;
  igraph_vector_t prev;
  igraph_real_t massx, massy;		/* The sum of the coordinates */
  long int vertices;		/* Number of active vertices  */
} igraph_2dgrid_t;

int igraph_2dgrid_init(igraph_2dgrid_t *grid, igraph_matrix_t *coords, 
		       igraph_real_t minx, igraph_real_t maxx, igraph_real_t deltax,
		       igraph_real_t miny, igraph_real_t maxy, igraph_real_t deltay);
void igraph_2dgrid_destroy(igraph_2dgrid_t *grid);
void igraph_2dgrid_add(igraph_2dgrid_t *grid, long int elem, 
		       igraph_real_t xc, igraph_real_t yc);
void igraph_2dgrid_add2(igraph_2dgrid_t *grid, long int elem);
void igraph_2dgrid_move(igraph_2dgrid_t *grid, long int elem, 
			igraph_real_t xc, igraph_real_t yc);
void igraph_2dgrid_getcenter(const igraph_2dgrid_t *grid, 
			     igraph_real_t *massx, igraph_real_t *massy);
igraph_bool_t igraph_2dgrid_in(const igraph_2dgrid_t *grid, long int elem);
igraph_real_t igraph_2dgrid_dist(const igraph_2dgrid_t *grid, 
			  long int e1, long int e2);
int igraph_2dgrid_neighbors(igraph_2dgrid_t *grid, igraph_vector_t *eids, 
			    igraph_integer_t vid, igraph_real_t r);

typedef struct igraph_2dgrid_iterator_t {
  long int vid, x, y;
  long int nei;
  long int nx[4], ny[4], ncells;
} igraph_2dgrid_iterator_t;

void igraph_2dgrid_reset(igraph_2dgrid_t *grid, igraph_2dgrid_iterator_t *it);
igraph_integer_t igraph_2dgrid_next(igraph_2dgrid_t *grid, 
			      igraph_2dgrid_iterator_t *it);
igraph_integer_t igraph_2dgrid_next_nei(igraph_2dgrid_t *grid,
				 igraph_2dgrid_iterator_t *it);

/* Another type of grid, each cell is owned by exactly one graph */

typedef struct igraph_i_layout_mergegrid_t {
  long int *data;
  long int stepsx, stepsy;
  igraph_real_t minx, maxx, deltax;
  igraph_real_t miny, maxy, deltay;
} igraph_i_layout_mergegrid_t;

int igraph_i_layout_mergegrid_init(igraph_i_layout_mergegrid_t *grid,
				   igraph_real_t minx, igraph_real_t maxx, long int stepsx,
				   igraph_real_t miny, igraph_real_t maxy, long int stepsy);
void igraph_i_layout_mergegrid_destroy(igraph_i_layout_mergegrid_t *grid);

int igraph_i_layout_merge_place_sphere(igraph_i_layout_mergegrid_t *grid,
				       igraph_real_t x, igraph_real_t y, igraph_real_t r,
				       long int id);

long int igraph_i_layout_mergegrid_get(igraph_i_layout_mergegrid_t *grid,
				       igraph_real_t x, igraph_real_t y);

long int igraph_i_layout_mergegrid_get_sphere(igraph_i_layout_mergegrid_t *g,
					      igraph_real_t x, igraph_real_t y, igraph_real_t r);

/* string -> string hash table */

typedef struct igraph_hashtable_t {
  igraph_trie_t keys;
  igraph_strvector_t elements;
  igraph_strvector_t defaults;
} igraph_hashtable_t;

int igraph_hashtable_init(igraph_hashtable_t *ht);
void igraph_hashtable_destroy(igraph_hashtable_t *ht);
int igraph_hashtable_addset(igraph_hashtable_t *ht,
			    const char *key, const char *def, 
			    const char *elem);
int igraph_hashtable_addset2(igraph_hashtable_t *ht,
			     const char *key, const char *def,
			     const char *elem, int elemlen);
int igraph_hashtable_get(igraph_hashtable_t *ht,
			 const char *key, char **elem);
int igraph_hashtable_getkeys(igraph_hashtable_t *ht, 
			     const igraph_strvector_t **sv);
int igraph_hashtable_reset(igraph_hashtable_t *ht);

/* Buckets, needed for the maximum flow algorithm */

typedef struct igraph_buckets_t {
  igraph_vector_long_t bptr;
  igraph_vector_long_t buckets;
  igraph_integer_t max, no;
} igraph_buckets_t;

int igraph_buckets_init(igraph_buckets_t *b, long int bsize, long int size);
void igraph_buckets_destroy(igraph_buckets_t *b);
void igraph_buckets_clear(igraph_buckets_t *b);
long int igraph_buckets_popmax(igraph_buckets_t *b);
long int igraph_buckets_pop(igraph_buckets_t *b, long int bucket);
igraph_bool_t igraph_buckets_empty(const igraph_buckets_t *b);
igraph_bool_t igraph_buckets_empty_bucket(const igraph_buckets_t *b, 
					  long int bucket);
void igraph_buckets_add(igraph_buckets_t *b, long int bucket,
			long int elem);

typedef struct igraph_dbuckets_t {
  igraph_vector_long_t bptr;
  igraph_vector_long_t next, prev;
  igraph_integer_t max, no;
} igraph_dbuckets_t;

int igraph_dbuckets_init(igraph_dbuckets_t *b, long int bsize, long int size);
void igraph_dbuckets_destroy(igraph_dbuckets_t *b);
void igraph_dbuckets_clear(igraph_dbuckets_t *b);
long int igraph_dbuckets_popmax(igraph_dbuckets_t *b);
long int igraph_dbuckets_pop(igraph_dbuckets_t *b, long int bucket);
igraph_bool_t igraph_dbuckets_empty(const igraph_dbuckets_t *b);
igraph_bool_t igraph_dbuckets_empty_bucket(const igraph_dbuckets_t *b, 
					   long int bucket);
void igraph_dbuckets_add(igraph_dbuckets_t *b, long int bucket,
			 long int elem);
void igraph_dbuckets_delete(igraph_dbuckets_t *b, long int bucket,
			    long int elem);

/* Special maximum heap, needed for the minimum cut algorithm */

typedef struct igraph_i_cutheap_t {
  igraph_vector_t heap;
  igraph_vector_t index;
  igraph_vector_t hptr;
  long int dnodes;
} igraph_i_cutheap_t;

int igraph_i_cutheap_init(igraph_i_cutheap_t *ch, igraph_integer_t nodes);
void igraph_i_cutheap_destroy(igraph_i_cutheap_t *ch);
igraph_bool_t igraph_i_cutheap_empty(igraph_i_cutheap_t *ch);
igraph_integer_t igraph_i_cutheap_active_size(igraph_i_cutheap_t *ch);
igraph_integer_t igraph_i_cutheap_size(igraph_i_cutheap_t *ch);
igraph_real_t igraph_i_cutheap_maxvalue(igraph_i_cutheap_t *ch);
igraph_integer_t igraph_i_cutheap_popmax(igraph_i_cutheap_t *ch);
int igraph_i_cutheap_update(igraph_i_cutheap_t *ch, igraph_integer_t index,
			    igraph_real_t add);
int igraph_i_cutheap_reset_undefine(igraph_i_cutheap_t *ch, long int vertex);

/* -------------------------------------------------- */
/* Flexible set                                       */
/* -------------------------------------------------- */

/** 
 * Set containing integer numbers regardless of the order
 * \ingroup types
 */

typedef struct s_set {
  igraph_integer_t* stor_begin;
  igraph_integer_t* stor_end;
  igraph_integer_t* end;
} igraph_set_t;

#define IGRAPH_SET_NULL { 0,0,0 }
#define IGRAPH_SET_INIT_FINALLY(v, size) \
  do { IGRAPH_CHECK(igraph_set_init(v, size)); \
  IGRAPH_FINALLY(igraph_set_destroy, v); } while (0)

int igraph_set_init      (igraph_set_t* set, long int size);
void igraph_set_destroy   (igraph_set_t* set);
igraph_bool_t igraph_set_inited   (igraph_set_t* set);
int igraph_set_reserve   (igraph_set_t* set, long int size);
igraph_bool_t igraph_set_empty     (const igraph_set_t* set);
void igraph_set_clear      (igraph_set_t* set);
long int igraph_set_size      (const igraph_set_t* set);
int igraph_set_add (igraph_set_t* v, igraph_integer_t e);
igraph_bool_t igraph_set_contains (igraph_set_t* set, igraph_integer_t e);
igraph_bool_t igraph_set_iterate (igraph_set_t* set, long int* state,
				  igraph_integer_t* element);

/* -------------------------------------------------- */
/* Vectorlist, fixed length                           */
/* -------------------------------------------------- */

typedef struct igraph_fixed_vectorlist_t {
  igraph_vector_t *vecs;
  igraph_vector_ptr_t v;
  long int length;
} igraph_fixed_vectorlist_t;

void igraph_fixed_vectorlist_destroy(igraph_fixed_vectorlist_t *l);
int igraph_fixed_vectorlist_convert(igraph_fixed_vectorlist_t *l,
				    const igraph_vector_t *from,
				    long int size);

__END_DECLS

#endif