1 /* -*- mode: C -*- */ 2 /* 3 IGraph library. 4 Copyright (C) 2009-2020 The igraph development team 5 6 This program is free software; you can redistribute it and/or modify 7 it under the terms of the GNU General Public License as published by 8 the Free Software Foundation; either version 2 of the License, or 9 (at your option) any later version. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with this program; if not, write to the Free Software 18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19 02110-1301 USA 20 21 */ 22 23 #ifndef IGRAPH_CORE_INDHEAP_H 24 #define IGRAPH_CORE_INDHEAP_H 25 26 #include "igraph_decls.h" 27 #include "igraph_types.h" 28 #include "igraph_vector.h" 29 30 __BEGIN_DECLS 31 32 /* -------------------------------------------------- */ 33 /* Indexed heap */ 34 /* -------------------------------------------------- */ 35 36 /** 37 * Indexed heap data type. 38 * \ingroup internal 39 */ 40 41 typedef struct s_indheap { 42 igraph_real_t* stor_begin; 43 igraph_real_t* stor_end; 44 igraph_real_t* end; 45 int destroy; 46 long int* index_begin; 47 } igraph_indheap_t; 48 49 #define IGRAPH_INDHEAP_NULL { 0,0,0,0,0 } 50 51 int igraph_indheap_init (igraph_indheap_t* h, long int size); 52 int igraph_indheap_init_array (igraph_indheap_t *t, igraph_real_t* data, long int len); 53 void igraph_indheap_destroy (igraph_indheap_t* h); 54 int igraph_indheap_clear(igraph_indheap_t *h); 55 igraph_bool_t igraph_indheap_empty (igraph_indheap_t* h); 56 int igraph_indheap_push (igraph_indheap_t* h, igraph_real_t elem); 57 int igraph_indheap_push_with_index(igraph_indheap_t* h, long int idx, igraph_real_t elem); 58 int igraph_indheap_modify(igraph_indheap_t* h, long int idx, igraph_real_t elem); 59 igraph_real_t igraph_indheap_max (igraph_indheap_t* h); 60 igraph_real_t igraph_indheap_delete_max(igraph_indheap_t* h); 61 long int igraph_indheap_size (igraph_indheap_t* h); 62 int igraph_indheap_reserve (igraph_indheap_t* h, long int size); 63 long int igraph_indheap_max_index(igraph_indheap_t *h); 64 65 66 /* -------------------------------------------------- */ 67 /* Doubly indexed heap */ 68 /* -------------------------------------------------- */ 69 70 /* This is a heap containing double elements and 71 two indices, its intended usage is the storage of 72 weighted edges. 73 */ 74 75 /** 76 * Doubly indexed heap data type. 77 * \ingroup internal 78 */ 79 80 typedef struct s_indheap_d { 81 igraph_real_t* stor_begin; 82 igraph_real_t* stor_end; 83 igraph_real_t* end; 84 int destroy; 85 long int* index_begin; 86 long int* index2_begin; 87 } igraph_d_indheap_t; 88 89 90 #define IGRAPH_D_INDHEAP_NULL { 0,0,0,0,0,0 } 91 92 IGRAPH_PRIVATE_EXPORT int igraph_d_indheap_init(igraph_d_indheap_t *h, long int size); 93 IGRAPH_PRIVATE_EXPORT void igraph_d_indheap_destroy(igraph_d_indheap_t *h); 94 IGRAPH_PRIVATE_EXPORT igraph_bool_t igraph_d_indheap_empty(igraph_d_indheap_t *h); 95 IGRAPH_PRIVATE_EXPORT int igraph_d_indheap_push(igraph_d_indheap_t *h, igraph_real_t elem, 96 long int idx, long int idx2); 97 IGRAPH_PRIVATE_EXPORT igraph_real_t igraph_d_indheap_max(igraph_d_indheap_t *h); 98 IGRAPH_PRIVATE_EXPORT igraph_real_t igraph_d_indheap_delete_max(igraph_d_indheap_t *h); 99 IGRAPH_PRIVATE_EXPORT long int igraph_d_indheap_size(igraph_d_indheap_t *h); 100 IGRAPH_PRIVATE_EXPORT int igraph_d_indheap_reserve(igraph_d_indheap_t *h, long int size); 101 IGRAPH_PRIVATE_EXPORT void igraph_d_indheap_max_index(igraph_d_indheap_t *h, long int *idx, long int *idx2); 102 103 /* -------------------------------------------------- */ 104 /* Two-way indexed heap */ 105 /* -------------------------------------------------- */ 106 107 /* This is a smart indexed heap. In addition to the "normal" indexed heap 108 it allows to access every element through its index in O(1) time. 109 In other words, for this heap the _modify operation is O(1), the 110 normal heap does this in O(n) time.... */ 111 112 typedef struct igraph_2wheap_t { 113 long int size; 114 igraph_vector_t data; 115 igraph_vector_long_t index; 116 igraph_vector_long_t index2; 117 } igraph_2wheap_t; 118 119 IGRAPH_PRIVATE_EXPORT int igraph_2wheap_init(igraph_2wheap_t *h, long int size); 120 IGRAPH_PRIVATE_EXPORT void igraph_2wheap_destroy(igraph_2wheap_t *h); 121 IGRAPH_PRIVATE_EXPORT int igraph_2wheap_clear(igraph_2wheap_t *h); 122 IGRAPH_PRIVATE_EXPORT int igraph_2wheap_push_with_index(igraph_2wheap_t *h, 123 long int idx, igraph_real_t elem); 124 IGRAPH_PRIVATE_EXPORT igraph_bool_t igraph_2wheap_empty(const igraph_2wheap_t *h); 125 IGRAPH_PRIVATE_EXPORT long int igraph_2wheap_size(const igraph_2wheap_t *h); 126 IGRAPH_PRIVATE_EXPORT long int igraph_2wheap_max_size(const igraph_2wheap_t *h); 127 IGRAPH_PRIVATE_EXPORT igraph_real_t igraph_2wheap_max(const igraph_2wheap_t *h); 128 IGRAPH_PRIVATE_EXPORT long int igraph_2wheap_max_index(const igraph_2wheap_t *h); 129 IGRAPH_PRIVATE_EXPORT igraph_real_t igraph_2wheap_deactivate_max(igraph_2wheap_t *h); 130 IGRAPH_PRIVATE_EXPORT igraph_bool_t igraph_2wheap_has_elem(const igraph_2wheap_t *h, long int idx); 131 IGRAPH_PRIVATE_EXPORT igraph_bool_t igraph_2wheap_has_active(const igraph_2wheap_t *h, long int idx); 132 IGRAPH_PRIVATE_EXPORT igraph_real_t igraph_2wheap_get(const igraph_2wheap_t *h, long int idx); 133 IGRAPH_PRIVATE_EXPORT igraph_real_t igraph_2wheap_delete_max(igraph_2wheap_t *h); 134 IGRAPH_PRIVATE_EXPORT igraph_real_t igraph_2wheap_delete_max_index(igraph_2wheap_t *h, long int *idx); 135 IGRAPH_PRIVATE_EXPORT int igraph_2wheap_modify(igraph_2wheap_t *h, long int idx, igraph_real_t elem); 136 IGRAPH_PRIVATE_EXPORT int igraph_2wheap_check(igraph_2wheap_t *h); 137 138 __END_DECLS 139 140 #endif 141