1 /* -*- mode: C -*- */
2 /*
3 IGraph library.
4 Copyright (C) 2003-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 #include "igraph_types.h"
24
25 #include "core/cutheap.h"
26
27 #define PARENT(x) ((x)/2)
28 #define LEFTCHILD(x) ((x)*2+1)
29 #define RIGHTCHILD(x) ((x)*2)
30 #define INACTIVE IGRAPH_INFINITY
31 #define UNDEFINED 0.0
32 #define INDEXINC 1
33
igraph_i_cutheap_switch(igraph_i_cutheap_t * ch,long int hidx1,long int hidx2)34 static void igraph_i_cutheap_switch(igraph_i_cutheap_t *ch,
35 long int hidx1, long int hidx2) {
36 if (hidx1 != hidx2) {
37 long int idx1 = (long int) VECTOR(ch->index)[hidx1];
38 long int idx2 = (long int) VECTOR(ch->index)[hidx2];
39
40 igraph_real_t tmp = VECTOR(ch->heap)[hidx1];
41 VECTOR(ch->heap)[hidx1] = VECTOR(ch->heap)[hidx2];
42 VECTOR(ch->heap)[hidx2] = tmp;
43
44 VECTOR(ch->index)[hidx1] = idx2;
45 VECTOR(ch->index)[hidx2] = idx1;
46
47 VECTOR(ch->hptr)[idx1] = hidx2 + INDEXINC;
48 VECTOR(ch->hptr)[idx2] = hidx1 + INDEXINC;
49 }
50 }
51
igraph_i_cutheap_sink(igraph_i_cutheap_t * ch,long int hidx)52 static void igraph_i_cutheap_sink(igraph_i_cutheap_t *ch, long int hidx) {
53 long int size = igraph_vector_size(&ch->heap);
54 if (LEFTCHILD(hidx) >= size) {
55 /* leaf node */
56 } else if (RIGHTCHILD(hidx) == size ||
57 VECTOR(ch->heap)[LEFTCHILD(hidx)] >=
58 VECTOR(ch->heap)[RIGHTCHILD(hidx)]) {
59 /* sink to the left if needed */
60 if (VECTOR(ch->heap)[hidx] < VECTOR(ch->heap)[LEFTCHILD(hidx)]) {
61 igraph_i_cutheap_switch(ch, hidx, LEFTCHILD(hidx));
62 igraph_i_cutheap_sink(ch, LEFTCHILD(hidx));
63 }
64 } else {
65 /* sink to the right */
66 if (VECTOR(ch->heap)[hidx] < VECTOR(ch->heap)[RIGHTCHILD(hidx)]) {
67 igraph_i_cutheap_switch(ch, hidx, RIGHTCHILD(hidx));
68 igraph_i_cutheap_sink(ch, RIGHTCHILD(hidx));
69 }
70 }
71 }
72
igraph_i_cutheap_shift_up(igraph_i_cutheap_t * ch,long int hidx)73 static void igraph_i_cutheap_shift_up(igraph_i_cutheap_t *ch, long int hidx) {
74 if (hidx == 0 || VECTOR(ch->heap)[hidx] < VECTOR(ch->heap)[PARENT(hidx)]) {
75 /* at the top */
76 } else {
77 igraph_i_cutheap_switch(ch, hidx, PARENT(hidx));
78 igraph_i_cutheap_shift_up(ch, PARENT(hidx));
79 }
80 }
81
igraph_i_cutheap_init(igraph_i_cutheap_t * ch,igraph_integer_t nodes)82 int igraph_i_cutheap_init(igraph_i_cutheap_t *ch, igraph_integer_t nodes) {
83 ch->dnodes = nodes;
84 IGRAPH_VECTOR_INIT_FINALLY(&ch->heap, nodes); /* all zero */
85 IGRAPH_CHECK(igraph_vector_init_seq(&ch->index, 0, nodes - 1));
86 IGRAPH_FINALLY(igraph_vector_destroy, &ch->index);
87 IGRAPH_CHECK(igraph_vector_init_seq(&ch->hptr, INDEXINC, nodes + INDEXINC - 1));
88 IGRAPH_FINALLY_CLEAN(2);
89 return 0;
90 }
91
igraph_i_cutheap_destroy(igraph_i_cutheap_t * ch)92 void igraph_i_cutheap_destroy(igraph_i_cutheap_t *ch) {
93 igraph_vector_destroy(&ch->hptr);
94 igraph_vector_destroy(&ch->index);
95 igraph_vector_destroy(&ch->heap);
96 }
97
igraph_i_cutheap_empty(igraph_i_cutheap_t * ch)98 igraph_bool_t igraph_i_cutheap_empty(igraph_i_cutheap_t *ch) {
99 return igraph_vector_empty(&ch->heap);
100 }
101
102 /* Number of active vertices */
103
igraph_i_cutheap_active_size(igraph_i_cutheap_t * ch)104 igraph_integer_t igraph_i_cutheap_active_size(igraph_i_cutheap_t *ch) {
105 return (igraph_integer_t) igraph_vector_size(&ch->heap);
106 }
107
108 /* Number of all (defined) vertices */
109
igraph_i_cutheap_size(igraph_i_cutheap_t * ch)110 igraph_integer_t igraph_i_cutheap_size(igraph_i_cutheap_t *ch) {
111 return (igraph_integer_t) (ch->dnodes);
112 }
113
igraph_i_cutheap_maxvalue(igraph_i_cutheap_t * ch)114 igraph_real_t igraph_i_cutheap_maxvalue(igraph_i_cutheap_t *ch) {
115 return VECTOR(ch->heap)[0];
116 }
117
igraph_i_cutheap_popmax(igraph_i_cutheap_t * ch)118 igraph_integer_t igraph_i_cutheap_popmax(igraph_i_cutheap_t *ch) {
119 long int size = igraph_vector_size(&ch->heap);
120 igraph_integer_t maxindex = (igraph_integer_t) VECTOR(ch->index)[0];
121 /* put the last element to the top */
122 igraph_i_cutheap_switch(ch, 0, size - 1);
123 /* remove the last element */
124 VECTOR(ch->hptr)[(long int) igraph_vector_tail(&ch->index)] = INACTIVE;
125 igraph_vector_pop_back(&ch->heap);
126 igraph_vector_pop_back(&ch->index);
127 igraph_i_cutheap_sink(ch, 0);
128
129 return maxindex;
130 }
131
132 /* Update the value of an active vertex, if not active it will be ignored */
133
igraph_i_cutheap_update(igraph_i_cutheap_t * ch,igraph_integer_t index,igraph_real_t add)134 int igraph_i_cutheap_update(igraph_i_cutheap_t *ch, igraph_integer_t index,
135 igraph_real_t add) {
136 igraph_real_t hidx = VECTOR(ch->hptr)[(long int)index];
137 if (hidx != INACTIVE && hidx != UNDEFINED) {
138 long int hidx2 = (long int) (hidx - INDEXINC);
139 /* printf("updating vertex %li, heap index %li\n", (long int) index, hidx2); */
140 VECTOR(ch->heap)[hidx2] += add;
141 igraph_i_cutheap_sink(ch, hidx2);
142 igraph_i_cutheap_shift_up(ch, hidx2);
143 }
144 return 0;
145 }
146
147 /* Reset the value of all vertices to zero and make them active */
148
igraph_i_cutheap_reset_undefine(igraph_i_cutheap_t * ch,long int vertex)149 int igraph_i_cutheap_reset_undefine(igraph_i_cutheap_t *ch, long int vertex) {
150 long int i, j, n = igraph_vector_size(&ch->hptr);
151 /* undefine */
152 VECTOR(ch->hptr)[vertex] = UNDEFINED;
153 ch->dnodes -= 1;
154
155 IGRAPH_CHECK(igraph_vector_resize(&ch->heap, ch->dnodes));
156 igraph_vector_null(&ch->heap);
157
158 IGRAPH_CHECK(igraph_vector_resize(&ch->index, ch->dnodes));
159
160 j = 0;
161 for (i = 0; i < n; i++) {
162 if (VECTOR(ch->hptr)[i] != UNDEFINED) {
163 VECTOR(ch->index)[j] = i;
164 VECTOR(ch->hptr)[i] = j + INDEXINC;
165 j++;
166 }
167 }
168
169 return 0;
170 }
171