SHOGUN  v2.0.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
FibonacciHeap.cpp
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2011 Evgeniy Andreev (gsomix)
8  *
9  * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
10  */
11 
13 
14 using namespace shogun;
15 
16 CFibonacciHeap::CFibonacciHeap()
17 {
18  min_root = NULL;
19 
20  max_num_nodes = 0;
21  nodes = NULL;
22  Dn = 0;
23 
24  num_nodes = 0;
25  num_trees = 0;
26 }
27 
28 CFibonacciHeap::CFibonacciHeap(int32_t capacity)
29 {
30  min_root = NULL;
31 
32  max_num_nodes = capacity;
33  nodes = SG_MALLOC(FibonacciHeapNode* , max_num_nodes);
34  for(int32_t i = 0; i < max_num_nodes; i++)
35  {
36  nodes[i] = new FibonacciHeapNode;
37  clear_node(i);
38  }
39 
40  Dn = 1 + (int32_t)(CMath::log2(max_num_nodes));
41  A = SG_MALLOC(FibonacciHeapNode* , Dn);
42  for(int32_t i = 0; i < Dn; i++)
43  {
44  A[i] = NULL;
45  }
46 
47  num_nodes = 0;
48  num_trees = 0;
49 }
50 
51 CFibonacciHeap::~CFibonacciHeap()
52 {
53  for(int32_t i = 0; i < max_num_nodes; i++)
54  {
55  if(nodes[i] != NULL)
56  delete nodes[i];
57  }
58  SG_FREE(nodes);
59  SG_FREE(A);
60 }
61 
62 void CFibonacciHeap::insert(int32_t index, float64_t key)
63 {
64  if(index >= max_num_nodes || index < 0)
65  return;
66 
67  if(nodes[index]->index != -1)
68  return; // node is not empty
69 
70  // init "new" node in array
71  nodes[index]->child = NULL;
72  nodes[index]->parent = NULL;
73 
74  nodes[index]->rank = 0;
75  nodes[index]->index = index;
76  nodes[index]->key = key;
77  nodes[index]->marked = false;
78 
79  add_to_roots(nodes[index]);
80  num_nodes++;
81 }
82 
83 int32_t CFibonacciHeap::extract_min(float64_t &ret_key)
84 {
85  FibonacciHeapNode *min_node;
86  FibonacciHeapNode *child, *next_child;
87 
88  int32_t result;
89 
90  if(num_nodes == 0)
91  return -1;
92 
93  min_node = min_root;
94  if(min_node == NULL)
95  return -1; // heap is empty now
96 
97  child = min_node->child;
98  while(child != NULL && child->parent != NULL)
99  {
100  next_child = child->right;
101 
102  // delete current child from childs list
103  child->left->right = child->right;
104  child->right->left = child->left;
105 
106  add_to_roots(child);
107 
108  // next iteration
109  child = next_child;
110  }
111 
112  // delete minimun from root list
113  min_node->left->right = min_node->right;
114  min_node->right->left = min_node->left;
115 
116  num_trees--;
117 
118  if(min_node == min_node->right)
119  {
120  min_root = NULL; // remove last element
121  }
122  else
123  {
124  min_root = min_node->right;
125  consolidate();
126  }
127 
128  result = min_node->index;
129  ret_key = min_node->key;
130  clear_node(result);
131 
132  num_nodes--;
133 
134  return result;
135 }
136 
137 void CFibonacciHeap::clear()
138 {
139  min_root = NULL;
140 
141  // clear all nodes
142  for(int32_t i = 0; i < max_num_nodes; i++)
143  {
144  clear_node(i);
145  }
146 
147  num_nodes = 0;
148  num_trees = 0;
149 }
150 
151 int32_t CFibonacciHeap::get_key(int32_t index, float64_t &ret_key)
152 {
153  if(index >= max_num_nodes || index < 0)
154  return -1;
155  if(nodes[index]->index == -1)
156  return -1;
157 
158  int32_t result = nodes[index]->index;
159  ret_key = nodes[index]->key;
160 
161  return result;
162 }
163 
164 void CFibonacciHeap::decrease_key(int32_t index, float64_t key)
165 {
166  FibonacciHeapNode* parent;
167 
168  if(index >= max_num_nodes || index < 0)
169  return;
170  if(nodes[index]->index == -1)
171  return; // node is empty
172  if(key > nodes[index]->key)
173  return;
174 
175 
176  nodes[index]->key = key;
177 
178  parent = nodes[index]->parent;
179 
180  if(parent != NULL && nodes[index]->key < parent->key)
181  {
182  cut(nodes[index], parent);
183  cascading_cut(parent);
184  }
185 
186  if(nodes[index]->key < min_root->key)
187  min_root = nodes[index];
188 }
189 
190 
191 void CFibonacciHeap::add_to_roots(FibonacciHeapNode *up_node)
192 {
193  if(min_root == NULL)
194  {
195  // if heap is empty, node becomes circular root list
196  min_root = up_node;
197 
198  up_node->left = up_node;
199  up_node->right = up_node;
200  }
201  else
202  {
203  // insert node to root list
204  up_node->right = min_root->right;
205  up_node->left = min_root;
206 
207  up_node->left->right = up_node;
208  up_node->right->left = up_node;
209 
210  // nomination of new minimum node
211  if(up_node->key < min_root->key)
212  {
213  min_root = up_node;
214  }
215  }
216 
217  up_node->parent = NULL;
218  num_trees++;
219 }
220 
221 void CFibonacciHeap::consolidate()
222 {
223  FibonacciHeapNode *x, *y, *w;
224  int32_t d;
225 
226  for(int32_t i = 0; i < Dn; i++)
227  {
228  A[i] = NULL;
229  }
230 
231  min_root->left->right = NULL;
232  min_root->left = NULL;
233  w = min_root;
234 
235  do
236  {
237  x = w;
238  d = x->rank;
239  w = w->right;
240 
241  while(A[d] != NULL)
242  {
243  y = A[d];
244 
245  if(y->key < x->key)
246  {
247  FibonacciHeapNode *temp;
248 
249  temp = y;
250  y = x;
251  x = temp;
252  }
253 
254  link_nodes(y, x);
255 
256  A[d] = NULL;
257  d++;
258  }
259  A[d] = x;
260  }
261  while(w != NULL);
262 
263  min_root = NULL;
264  num_trees = 0;
265 
266  for(int32_t i = 0; i < Dn; i++)
267  {
268  if(A[i] != NULL)
269  {
270  A[i]->marked = false;
271  add_to_roots(A[i]);
272  }
273  }
274 }
275 
276 void CFibonacciHeap::link_nodes(FibonacciHeapNode *y, FibonacciHeapNode *x)
277 {
278  if(y->right != NULL)
279  y->right->left = y->left;
280  if(y->left != NULL)
281  y->left->right = y->right;
282 
283  num_trees--;
284 
285  y->left = y;
286  y->right = y;
287 
288  y->parent = x;
289 
290  if(x->child == NULL)
291  {
292  x->child = y;
293  }
294  else
295  {
296  y->left = x->child;
297  y->right = x->child->right;
298 
299  x->child->right = y;
300  y->right->left = y;
301  }
302 
303  x->rank++;
304 
305  y->marked = false;
306 }
307 
308 void CFibonacciHeap::clear_node(int32_t index)
309 {
310  nodes[index]->parent = NULL;
311  nodes[index]->child = NULL;
312  nodes[index]->left = NULL;
313  nodes[index]->right = NULL;
314 
315  nodes[index]->rank = 0;
316  nodes[index]->index = -1;
317  nodes[index]->key = 0;
318 
319  nodes[index]->marked = false;
320 }
321 
322 void CFibonacciHeap::cut(FibonacciHeapNode *child, FibonacciHeapNode *parent)
323 {
324  if(parent->child == child)
325  parent->child = child->right;
326 
327  if(parent->child == child)
328  parent->child = NULL;
329 
330  parent->rank--;
331 
332  child->left->right = child->right;
333  child->right->left = child->left;
334  child->marked = false;
335 
336  add_to_roots(child);
337 }
338 
339 void CFibonacciHeap::cascading_cut(FibonacciHeapNode *tree)
340 {
341  FibonacciHeapNode *temp;
342 
343  temp = tree->parent;
344  if(temp != NULL)
345  {
346  if(!tree->marked)
347  {
348  tree->marked = true;
349  }
350  else
351  {
352  cut(tree, temp);
353  cascading_cut(temp);
354  }
355  }
356 }
357 
358 void CFibonacciHeap::debug_print()
359 {
360  SG_SPRINT("%d %d\n", num_trees, num_nodes);
361  for(int32_t i = 0; i < max_num_nodes; i++)
362  {
363  if(nodes[i]->index == -1)
364  {
365  SG_SPRINT("None\n");
366  }
367  else
368  {
369  SG_SPRINT("%f\n",nodes[i]->key);
370  }
371  }
372 }

SHOGUN Machine Learning Toolbox - Documentation