4
Copyright (C) 2003, 2004 Gabor Csardi <csardi@rmki.kfki.hu>
5
MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
7
This program is free software; you can redistribute it and/or modify
8
it under the terms of the GNU General Public License as published by
9
the Free Software Foundation; either version 2 of the License, or
10
(at your option) any later version.
12
This program is distributed in the hope that it will be useful,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
GNU General Public License for more details.
17
You should have received a copy of the GNU General Public License
18
along with this program; if not, write to the Free Software
19
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
30
# define __BEGIN_DECLS extern "C" {
31
# define __END_DECLS }
33
# define __BEGIN_DECLS /* empty */
34
# define __END_DECLS /* empty */
47
typedef double igraph_integer_t;
48
typedef double igraph_real_t;
49
typedef int igraph_bool_t;
51
/* -------------------------------------------------- */
52
/* double ended queue, very useful */
53
/* -------------------------------------------------- */
55
#define BASE_IGRAPH_REAL
56
#include "igraph_pmt.h"
58
#include "igraph_pmt_off.h"
59
#undef BASE_IGRAPH_REAL
62
#include "igraph_pmt.h"
64
#include "igraph_pmt_off.h"
68
#include "igraph_pmt.h"
70
#include "igraph_pmt_off.h"
74
#include "igraph_pmt.h"
76
#include "igraph_pmt_off.h"
79
#define IGRAPH_DQUEUE_NULL { 0,0,0,0 }
80
#define IGRAPH_DQUEUE_INIT_FINALLY(v, size) \
81
do { IGRAPH_CHECK(igraph_dqueue_init(v, size)); \
82
IGRAPH_FINALLY(igraph_dqueue_destroy, v); } while (0)
84
/* -------------------------------------------------- */
86
/* -------------------------------------------------- */
88
#define BASE_IGRAPH_REAL
89
#include "igraph_pmt.h"
91
#include "igraph_pmt_off.h"
92
#undef BASE_IGRAPH_REAL
95
#include "igraph_pmt.h"
97
#include "igraph_pmt_off.h"
101
#include "igraph_pmt.h"
103
#include "igraph_pmt_off.h"
107
#include "igraph_pmt.h"
109
#include "igraph_pmt_off.h"
112
/* These are for internal use only */
113
int igraph_vector_order(const igraph_vector_t* v, const igraph_vector_t *v2,
114
igraph_vector_t* res, igraph_real_t maxval);
115
int igraph_vector_order1(const igraph_vector_t* v,
116
igraph_vector_t* res, igraph_real_t maxval);
117
int igraph_vector_order2(igraph_vector_t *v);
118
int igraph_vector_rank(const igraph_vector_t *v, igraph_vector_t *res,
121
/* -------------------------------------------------- */
122
/* Matrix, very similar to vector */
123
/* -------------------------------------------------- */
125
#define BASE_IGRAPH_REAL
126
#include "igraph_pmt.h"
128
#include "igraph_pmt_off.h"
129
#undef BASE_IGRAPH_REAL
132
#include "igraph_pmt.h"
134
#include "igraph_pmt_off.h"
138
#include "igraph_pmt.h"
140
#include "igraph_pmt_off.h"
144
#include "igraph_pmt.h"
146
#include "igraph_pmt_off.h"
149
#define IGRAPH_MATRIX_NULL { IGRAPH_VECTOR_NULL, 0, 0 }
150
#define IGRAPH_MATRIX_INIT_FINALLY(m, nr, nc) \
151
do { IGRAPH_CHECK(igraph_matrix_init(m, nr, nc)); \
152
IGRAPH_FINALLY(igraph_matrix_destroy, m); } while (0)
157
* \brief Accessing an element of a matrix.
159
* Note that there are no range checks right now.
160
* This functionality might be redefines as a proper function later.
161
* \param m The matrix object.
162
* \param i The index of the row, starting with zero.
163
* \param j The index of the column, starting with zero.
165
* Time complexity: O(1).
167
#define MATRIX(m,i,j) ((m).data.stor_begin[(m).nrow*(j)+(i)])
169
/* -------------------------------------------------- */
170
/* Flexible vector, storing pointers */
171
/* -------------------------------------------------- */
174
* Vector, storing pointers efficiently
178
typedef struct s_vector_ptr {
182
} igraph_vector_ptr_t;
184
#define IGRAPH_VECTOR_PTR_NULL { 0,0,0 }
185
#define IGRAPH_VECTOR_PTR_INIT_FINALLY(v, size) \
186
do { IGRAPH_CHECK(igraph_vector_ptr_init(v, size)); \
187
IGRAPH_FINALLY(igraph_vector_ptr_destroy, v); } while (0)
189
int igraph_vector_ptr_init (igraph_vector_ptr_t* v, long int size);
190
int igraph_vector_ptr_init_copy (igraph_vector_ptr_t* v, void** data, long int length);
191
const igraph_vector_ptr_t *igraph_vector_ptr_view (const igraph_vector_ptr_t *v,
192
void *const *data, long int length);
193
void igraph_vector_ptr_destroy (igraph_vector_ptr_t* v);
194
void igraph_vector_ptr_free_all (igraph_vector_ptr_t* v);
195
void igraph_vector_ptr_destroy_all (igraph_vector_ptr_t* v);
196
int igraph_vector_ptr_reserve (igraph_vector_ptr_t* v, long int size);
197
igraph_bool_t igraph_vector_ptr_empty (const igraph_vector_ptr_t* v);
198
long int igraph_vector_ptr_size (const igraph_vector_ptr_t* v);
199
void igraph_vector_ptr_clear (igraph_vector_ptr_t* v);
200
void igraph_vector_ptr_null (igraph_vector_ptr_t* v);
201
int igraph_vector_ptr_push_back (igraph_vector_ptr_t* v, void* e);
202
void *igraph_vector_ptr_pop_back (igraph_vector_ptr_t *v);
203
int igraph_vector_ptr_insert(igraph_vector_ptr_t *v, long int pos, void* e);
204
void* igraph_vector_ptr_e (const igraph_vector_ptr_t* v, long int pos);
205
void igraph_vector_ptr_set (igraph_vector_ptr_t* v, long int pos, void* value);
206
int igraph_vector_ptr_resize(igraph_vector_ptr_t* v, long int newsize);
207
void igraph_vector_ptr_copy_to(const igraph_vector_ptr_t *v, void** to);
208
int igraph_vector_ptr_copy(igraph_vector_ptr_t *to, const igraph_vector_ptr_t *from);
209
void igraph_vector_ptr_remove(igraph_vector_ptr_t *v, long int pos);
210
void igraph_vector_ptr_sort(igraph_vector_ptr_t *v, int(*compar)(const void*, const void*));
212
/* -------------------------------------------------- */
214
/* -------------------------------------------------- */
217
* \section about_igraph_spmatrix_t_objects About \type igraph_spmatrix_t objects
219
* <para>The \type igraph_spmatrix_t type stores a sparse matrix with the
220
* assumption that the number of nonzero elements in the matrix scales
221
* linearly with the row or column count of the matrix (so most of the
222
* elements are zero). Of course it can store an arbitrary real matrix,
223
* but if most of the elements are nonzero, one should use \type igraph_matrix_t
226
* <para>The elements are stored in column compressed format, so the elements
227
* in the same column are stored adjacent in the computer's memory. The storage
228
* requirement for a sparse matrix is O(n) where n is the number of nonzero
229
* elements. Actually it can be a bit larger, see the documentation of
230
* the vector type for an explanation.</para>
232
typedef struct s_spmatrix {
233
igraph_vector_t ridx, cidx, data;
237
#define IGRAPH_SPMATRIX_INIT_FINALLY(m, nr, nc) \
238
do { IGRAPH_CHECK(igraph_spmatrix_init(m, nr, nc)); \
239
IGRAPH_FINALLY(igraph_spmatrix_destroy, m); } while (0)
241
int igraph_spmatrix_init(igraph_spmatrix_t *m, long int nrow, long int ncol);
242
void igraph_spmatrix_destroy(igraph_spmatrix_t *m);
243
int igraph_spmatrix_resize(igraph_spmatrix_t *m, long int nrow, long int ncol);
244
igraph_real_t igraph_spmatrix_e(const igraph_spmatrix_t *m, long int row, long int col);
245
int igraph_spmatrix_set(igraph_spmatrix_t *m, long int row, long int col,
246
igraph_real_t value);
247
int igraph_spmatrix_add_e(igraph_spmatrix_t *m, long int row, long int col,
248
igraph_real_t value);
249
int igraph_spmatrix_add_col_values(igraph_spmatrix_t *m, long int to, long int from);
250
long int igraph_spmatrix_count_nonzero(const igraph_spmatrix_t *m);
251
long int igraph_spmatrix_size(const igraph_spmatrix_t *m);
252
long int igraph_spmatrix_nrow(const igraph_spmatrix_t *m);
253
long int igraph_spmatrix_ncol(const igraph_spmatrix_t *m);
254
int igraph_spmatrix_copy_to(const igraph_spmatrix_t *m, igraph_real_t *to);
255
int igraph_spmatrix_null(igraph_spmatrix_t *m);
256
int igraph_spmatrix_add_cols(igraph_spmatrix_t *m, long int n);
257
int igraph_spmatrix_add_rows(igraph_spmatrix_t *m, long int n);
258
int igraph_spmatrix_clear_col(igraph_spmatrix_t *m, long int col);
259
int igraph_spmatrix_clear_row(igraph_spmatrix_t *m, long int row);
260
int igraph_spmatrix_copy(igraph_spmatrix_t *to, const igraph_spmatrix_t *from);
261
igraph_real_t igraph_spmatrix_max_nonzero(const igraph_spmatrix_t *m,
262
igraph_real_t *ridx, igraph_real_t *cidx);
263
igraph_real_t igraph_spmatrix_max(const igraph_spmatrix_t *m,
264
igraph_real_t *ridx, igraph_real_t *cidx);
265
void igraph_spmatrix_scale(igraph_spmatrix_t *m, igraph_real_t by);
266
int igraph_spmatrix_colsums(const igraph_spmatrix_t *m, igraph_vector_t *res);
268
int igraph_i_spmatrix_get_col_nonzero_indices(const igraph_spmatrix_t *m,
269
igraph_vector_t *res, long int col);
270
int igraph_i_spmatrix_clear_row_fast(igraph_spmatrix_t *m, long int row);
271
int igraph_i_spmatrix_cleanup(igraph_spmatrix_t *m);
273
/* -------------------------------------------------- */
275
/* -------------------------------------------------- */
277
#define BASE_IGRAPH_REAL
278
#include "igraph_pmt.h"
280
#include "igraph_pmt_off.h"
281
#undef BASE_IGRAPH_REAL
284
#include "igraph_pmt.h"
286
#include "igraph_pmt_off.h"
290
#include "igraph_pmt.h"
292
#include "igraph_pmt_off.h"
296
#include "igraph_pmt.h"
298
#include "igraph_pmt_off.h"
301
/* -------------------------------------------------- */
303
/* -------------------------------------------------- */
305
#define BASE_IGRAPH_REAL
306
#include "igraph_pmt.h"
308
#include "igraph_pmt_off.h"
309
#undef BASE_IGRAPH_REAL
312
#include "igraph_pmt.h"
314
#include "igraph_pmt_off.h"
318
#include "igraph_pmt.h"
320
#include "igraph_pmt_off.h"
324
#include "igraph_pmt.h"
326
#include "igraph_pmt_off.h"
329
#define IGRAPH_STACK_NULL { 0,0,0 }
331
/* -------------------------------------------------- */
333
/* -------------------------------------------------- */
340
#define BASE_IGRAPH_REAL
341
#define HEAP_TYPE_MAX
342
#include "igraph_pmt.h"
344
#include "igraph_pmt_off.h"
346
#define HEAP_TYPE_MIN
347
#include "igraph_pmt.h"
349
#include "igraph_pmt_off.h"
351
#undef BASE_IGRAPH_REAL
354
#define HEAP_TYPE_MAX
355
#include "igraph_pmt.h"
357
#include "igraph_pmt_off.h"
359
#define HEAP_TYPE_MIN
360
#include "igraph_pmt.h"
362
#include "igraph_pmt_off.h"
367
#define HEAP_TYPE_MAX
368
#include "igraph_pmt.h"
370
#include "igraph_pmt_off.h"
372
#define HEAP_TYPE_MIN
373
#include "igraph_pmt.h"
375
#include "igraph_pmt_off.h"
379
#define IGRAPH_HEAP_NULL { 0,0,0 }
381
/* -------------------------------------------------- */
383
/* -------------------------------------------------- */
386
* Indexed heap data type.
390
typedef struct s_indheap {
391
igraph_real_t* stor_begin;
392
igraph_real_t* stor_end;
395
long int* index_begin;
398
#define IGRAPH_INDHEAP_NULL { 0,0,0,0,0 }
400
int igraph_indheap_init (igraph_indheap_t* h, long int size);
401
int igraph_indheap_init_array (igraph_indheap_t *t, igraph_real_t* data, long int len);
402
void igraph_indheap_destroy (igraph_indheap_t* h);
403
int igraph_indheap_clear(igraph_indheap_t *h);
404
igraph_bool_t igraph_indheap_empty (igraph_indheap_t* h);
405
int igraph_indheap_push (igraph_indheap_t* h, igraph_real_t elem);
406
int igraph_indheap_push_with_index(igraph_indheap_t* h, long int idx, igraph_real_t elem);
407
int igraph_indheap_modify(igraph_indheap_t* h, long int idx, igraph_real_t elem);
408
igraph_real_t igraph_indheap_max (igraph_indheap_t* h);
409
igraph_real_t igraph_indheap_delete_max(igraph_indheap_t* h);
410
long int igraph_indheap_size (igraph_indheap_t* h);
411
int igraph_indheap_reserve (igraph_indheap_t* h, long int size);
412
long int igraph_indheap_max_index(igraph_indheap_t *h);
414
void igraph_indheap_i_build(igraph_indheap_t* h, long int head);
415
void igraph_indheap_i_shift_up(igraph_indheap_t* h, long int elem);
416
void igraph_indheap_i_sink(igraph_indheap_t* h, long int head);
417
void igraph_indheap_i_switch(igraph_indheap_t* h, long int e1, long int e2);
419
/* -------------------------------------------------- */
420
/* Doubly indexed heap */
421
/* -------------------------------------------------- */
423
/* This is a heap containing double elements and
424
two indices, its intended usage is the storage of
429
* Doubly indexed heap data type.
433
typedef struct s_indheap_d {
434
igraph_real_t* stor_begin;
435
igraph_real_t* stor_end;
438
long int* index_begin;
439
long int* index2_begin;
440
} igraph_d_indheap_t;
443
#define IGRAPH_D_INDHEAP_NULL { 0,0,0,0,0,0 }
445
int igraph_d_indheap_init (igraph_d_indheap_t* h, long int size);
446
void igraph_d_indheap_destroy (igraph_d_indheap_t* h);
447
igraph_bool_t igraph_d_indheap_empty (igraph_d_indheap_t* h);
448
int igraph_d_indheap_push (igraph_d_indheap_t* h, igraph_real_t elem,
449
long int idx, long int idx2);
450
igraph_real_t igraph_d_indheap_max (igraph_d_indheap_t* h);
451
igraph_real_t igraph_d_indheap_delete_max(igraph_d_indheap_t* h);
452
long int igraph_d_indheap_size (igraph_d_indheap_t* h);
453
int igraph_d_indheap_reserve (igraph_d_indheap_t* h, long int size);
454
void igraph_d_indheap_max_index(igraph_d_indheap_t *h, long int *idx, long int *idx2);
456
void igraph_d_indheap_i_build(igraph_d_indheap_t* h, long int head);
457
void igraph_d_indheap_i_shift_up(igraph_d_indheap_t* h, long int elem);
458
void igraph_d_indheap_i_sink(igraph_d_indheap_t* h, long int head);
459
void igraph_d_indheap_i_switch(igraph_d_indheap_t* h, long int e1, long int e2);
466
typedef struct s_igraph_strvector {
469
} igraph_strvector_t;
473
* Indexing string vectors
475
* This is a macro which allows to query the elements of a string vector in
476
* simpler way than \ref igraph_strvector_get(). Note this macro cannot be
477
* used to set an element, for that use \ref igraph_strvector_set().
478
* \param sv The string vector
479
* \param i The the index of the element.
480
* \return The element at position \p i.
482
* Time complexity: O(1).
484
#define STR(sv,i) ((const char *)((sv).data[(i)]))
486
#define IGRAPH_STRVECTOR_NULL { 0,0 }
487
#define IGRAPH_STRVECTOR_INIT_FINALLY(v, size) \
488
do { IGRAPH_CHECK(igraph_strvector_init(v, size)); \
489
IGRAPH_FINALLY( (igraph_finally_func_t*) igraph_strvector_destroy, v); } while (0)
491
int igraph_strvector_init(igraph_strvector_t *sv, long int len);
492
void igraph_strvector_destroy(igraph_strvector_t *sv);
493
long int igraph_strvector_size(const igraph_strvector_t *sv);
494
void igraph_strvector_get(const igraph_strvector_t *sv,
495
long int idx, char **value);
496
int igraph_strvector_set(igraph_strvector_t *sv, long int idx,
498
int igraph_strvector_set2(igraph_strvector_t *sv, long int idx,
499
const char *value, int len);
500
void igraph_strvector_clear(igraph_strvector_t *sv);
501
void igraph_strvector_remove_section(igraph_strvector_t *v, long int from,
503
void igraph_strvector_remove(igraph_strvector_t *v, long int elem);
504
void igraph_strvector_move_interval(igraph_strvector_t *v, long int begin,
505
long int end, long int to);
506
int igraph_strvector_copy(igraph_strvector_t *to,
507
const igraph_strvector_t *from);
508
int igraph_strvector_append(igraph_strvector_t *to,
509
const igraph_strvector_t *from);
510
int igraph_strvector_resize(igraph_strvector_t* v, long int newsize);
511
int igraph_strvector_add(igraph_strvector_t *v, const char *value);
512
void igraph_strvector_permdelete(igraph_strvector_t *v, const igraph_vector_t *index,
514
void igraph_strvector_remove_negidx(igraph_strvector_t *v, const igraph_vector_t *neg,
522
typedef struct s_igraph_trie_node {
523
igraph_strvector_t strs;
524
igraph_vector_ptr_t children;
525
igraph_vector_t values;
526
} igraph_trie_node_t;
528
typedef struct s_igraph_trie {
529
igraph_strvector_t strs;
530
igraph_vector_ptr_t children;
531
igraph_vector_t values;
533
igraph_bool_t storekeys;
534
igraph_strvector_t keys;
537
#define IGRAPH_TRIE_NULL { IGRAPH_STRVECTOR_NULL, IGRAPH_VECTOR_PTR_NULL, \
538
IGRAPH_VECTOR_NULL, 0, 0, IGRAPH_STRVECTOR_NULL }
539
#define IGRAPH_TRIE_INIT_FINALLY(tr, sk) \
540
do { IGRAPH_CHECK(igraph_trie_init(tr, sk)); \
541
IGRAPH_FINALLY(igraph_trie_destroy, tr); } while (0)
543
int igraph_trie_init(igraph_trie_t *t, igraph_bool_t storekeys);
544
void igraph_trie_destroy(igraph_trie_t *t);
545
int igraph_trie_get(igraph_trie_t *t, const char *key, long int *id);
546
int igraph_trie_check(igraph_trie_t *t, const char *key, long int *id);
547
int igraph_trie_get2(igraph_trie_t *t, const char *key, long int length,
549
void igraph_trie_idx(igraph_trie_t *t, long int idx, char **str);
550
int igraph_trie_getkeys(igraph_trie_t *t, const igraph_strvector_t **strv);
551
long int igraph_trie_size(igraph_trie_t *t);
558
int igraph_psumtree_init(igraph_psumtree_t *t, long int size);
559
void igraph_psumtree_destroy(igraph_psumtree_t *t);
560
igraph_real_t igraph_psumtree_get(const igraph_psumtree_t *t, long int idx);
561
long int igraph_psumtree_size(const igraph_psumtree_t *t);
562
int igraph_psumtree_search(const igraph_psumtree_t *t, long int *idx,
564
int igraph_psumtree_update(igraph_psumtree_t *t, long int idx,
565
igraph_real_t new_value);
566
igraph_real_t igraph_psumtree_sum(const igraph_psumtree_t *t);
569
* 2d grid containing points
572
typedef struct igraph_2dgrid_t {
573
igraph_matrix_t *coords;
574
igraph_real_t minx, maxx, deltax;
575
igraph_real_t miny, maxy, deltay;
576
long int stepsx, stepsy;
577
igraph_matrix_t startidx;
578
igraph_vector_t next;
579
igraph_vector_t prev;
580
igraph_real_t massx, massy; /* The sum of the coordinates */
581
long int vertices; /* Number of active vertices */
584
int igraph_2dgrid_init(igraph_2dgrid_t *grid, igraph_matrix_t *coords,
585
igraph_real_t minx, igraph_real_t maxx, igraph_real_t deltax,
586
igraph_real_t miny, igraph_real_t maxy, igraph_real_t deltay);
587
void igraph_2dgrid_destroy(igraph_2dgrid_t *grid);
588
void igraph_2dgrid_add(igraph_2dgrid_t *grid, long int elem,
589
igraph_real_t xc, igraph_real_t yc);
590
void igraph_2dgrid_add2(igraph_2dgrid_t *grid, long int elem);
591
void igraph_2dgrid_move(igraph_2dgrid_t *grid, long int elem,
592
igraph_real_t xc, igraph_real_t yc);
593
void igraph_2dgrid_getcenter(const igraph_2dgrid_t *grid,
594
igraph_real_t *massx, igraph_real_t *massy);
595
igraph_bool_t igraph_2dgrid_in(const igraph_2dgrid_t *grid, long int elem);
596
igraph_real_t igraph_2dgrid_dist(const igraph_2dgrid_t *grid,
597
long int e1, long int e2);
598
int igraph_2dgrid_neighbors(igraph_2dgrid_t *grid, igraph_vector_t *eids,
599
igraph_integer_t vid, igraph_real_t r);
601
typedef struct igraph_2dgrid_iterator_t {
604
long int nx[4], ny[4], ncells;
605
} igraph_2dgrid_iterator_t;
607
void igraph_2dgrid_reset(igraph_2dgrid_t *grid, igraph_2dgrid_iterator_t *it);
608
igraph_integer_t igraph_2dgrid_next(igraph_2dgrid_t *grid,
609
igraph_2dgrid_iterator_t *it);
610
igraph_integer_t igraph_2dgrid_next_nei(igraph_2dgrid_t *grid,
611
igraph_2dgrid_iterator_t *it);
613
/* Another type of grid, each cell is owned by exactly one graph */
615
typedef struct igraph_i_layout_mergegrid_t {
617
long int stepsx, stepsy;
618
igraph_real_t minx, maxx, deltax;
619
igraph_real_t miny, maxy, deltay;
620
} igraph_i_layout_mergegrid_t;
622
int igraph_i_layout_mergegrid_init(igraph_i_layout_mergegrid_t *grid,
623
igraph_real_t minx, igraph_real_t maxx, long int stepsx,
624
igraph_real_t miny, igraph_real_t maxy, long int stepsy);
625
void igraph_i_layout_mergegrid_destroy(igraph_i_layout_mergegrid_t *grid);
627
int igraph_i_layout_merge_place_sphere(igraph_i_layout_mergegrid_t *grid,
628
igraph_real_t x, igraph_real_t y, igraph_real_t r,
631
long int igraph_i_layout_mergegrid_get(igraph_i_layout_mergegrid_t *grid,
632
igraph_real_t x, igraph_real_t y);
634
long int igraph_i_layout_mergegrid_get_sphere(igraph_i_layout_mergegrid_t *g,
635
igraph_real_t x, igraph_real_t y, igraph_real_t r);
637
/* string -> string hash table */
639
typedef struct igraph_hashtable_t {
641
igraph_strvector_t elements;
642
igraph_strvector_t defaults;
643
} igraph_hashtable_t;
645
int igraph_hashtable_init(igraph_hashtable_t *ht);
646
void igraph_hashtable_destroy(igraph_hashtable_t *ht);
647
int igraph_hashtable_addset(igraph_hashtable_t *ht,
648
const char *key, const char *def,
650
int igraph_hashtable_addset2(igraph_hashtable_t *ht,
651
const char *key, const char *def,
652
const char *elem, int elemlen);
653
int igraph_hashtable_get(igraph_hashtable_t *ht,
654
const char *key, char **elem);
655
int igraph_hashtable_getkeys(igraph_hashtable_t *ht,
656
const igraph_strvector_t **sv);
657
int igraph_hashtable_reset(igraph_hashtable_t *ht);
659
/* Buckets, needed for the maximum flow algorithm */
661
typedef struct igraph_buckets_t {
662
igraph_vector_t bptr;
663
igraph_vector_t buckets;
664
igraph_integer_t max, no;
667
int igraph_buckets_init(igraph_buckets_t *b, long int bsize, long int size);
668
void igraph_buckets_destroy(igraph_buckets_t *b);
669
long int igraph_buckets_popmax(igraph_buckets_t *b);
670
igraph_bool_t igraph_buckets_empty(const igraph_buckets_t *b);
671
void igraph_buckets_add(igraph_buckets_t *b, long int bucket,
674
/* Special maximum heap, needed for the minimum cut algorithm */
676
typedef struct igraph_i_cutheap_t {
677
igraph_vector_t heap;
678
igraph_vector_t index;
679
igraph_vector_t hptr;
681
} igraph_i_cutheap_t;
683
int igraph_i_cutheap_init(igraph_i_cutheap_t *ch, igraph_integer_t nodes);
684
void igraph_i_cutheap_destroy(igraph_i_cutheap_t *ch);
685
igraph_bool_t igraph_i_cutheap_empty(igraph_i_cutheap_t *ch);
686
igraph_integer_t igraph_i_cutheap_active_size(igraph_i_cutheap_t *ch);
687
igraph_integer_t igraph_i_cutheap_size(igraph_i_cutheap_t *ch);
688
igraph_real_t igraph_i_cutheap_maxvalue(igraph_i_cutheap_t *ch);
689
igraph_integer_t igraph_i_cutheap_popmax(igraph_i_cutheap_t *ch);
690
int igraph_i_cutheap_update(igraph_i_cutheap_t *ch, igraph_integer_t index,
692
int igraph_i_cutheap_reset_undefine(igraph_i_cutheap_t *ch, long int vertex);
694
/* -------------------------------------------------- */
696
/* -------------------------------------------------- */
699
* Set containing integer numbers regardless of the order
703
typedef struct s_set {
704
igraph_real_t* stor_begin;
705
igraph_real_t* stor_end;
709
#define IGRAPH_SET_NULL { 0,0,0 }
710
#define IGRAPH_SET_INIT_FINALLY(v, size) \
711
do { IGRAPH_CHECK(igraph_set_init(v, size)); \
712
IGRAPH_FINALLY(igraph_set_destroy, v); } while (0)
714
int igraph_set_init (igraph_set_t* set, long int size);
715
void igraph_set_destroy (igraph_set_t* set);
716
igraph_bool_t igraph_set_inited (igraph_set_t* set);
717
int igraph_set_reserve (igraph_set_t* set, long int size);
718
igraph_bool_t igraph_set_empty (const igraph_set_t* set);
719
void igraph_set_clear (igraph_set_t* set);
720
long int igraph_set_size (const igraph_set_t* set);
721
int igraph_set_add (igraph_set_t* v, igraph_integer_t e);
722
igraph_bool_t igraph_set_contains (igraph_set_t* set, igraph_integer_t e);
723
igraph_bool_t igraph_set_iterate (igraph_set_t* set, long int* state,
724
igraph_integer_t* element);
726
#if defined(INFINITY)
727
# define IGRAPH_INFINITY INFINITY
728
# define IGRAPH_POSINFINITY INFINITY
729
# define IGRAPH_NEGINFINITY (-INFINITY)
731
# define IGRAPH_INFINITY (igraph_i_fdiv(1.0, 0.0))
732
# define IGRAPH_POSINFINITY (igraph_i_fdiv(1.0, 0.0))
733
# define IGRAPH_NEGINFINITY (igraph_i_fdiv(-1.0, 0.0))
736
int igraph_finite(double x);
737
#define IGRAPH_FINITE(x) igraph_finite(x)
740
# define IGRAPH_NAN NAN
741
#elif defined(INFINITY)
742
# define IGRAPH_NAN (INFINITY/INFINITY)
744
# define IGRAPH_NAN (igraph_i_fdiv(0.0, 0.0))