FibonacciHeap.cpp

Go to the documentation of this file.
00001 /*
00002  * This program is free software; you can redistribute it and/or modify
00003  * it under the terms of the GNU General Public License as published by
00004  * the Free Software Foundation; either version 3 of the License, or
00005  * (at your option) any later version.
00006  *
00007  * Written (W) 2011 Evgeniy Andreev (gsomix)
00008  *
00009  * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
00010  */
00011 
00012 #include <shogun/lib/FibonacciHeap.h>
00013 
00014 using namespace shogun;
00015 
00016 CFibonacciHeap::CFibonacciHeap()
00017 {
00018     min_root = NULL;
00019 
00020     max_num_nodes = 0;
00021     nodes = NULL;
00022     Dn = 0;
00023 
00024     num_nodes = 0;
00025     num_trees = 0;
00026 }
00027 
00028 CFibonacciHeap::CFibonacciHeap(int32_t capacity)
00029 {
00030     min_root = NULL;
00031 
00032     max_num_nodes = capacity;
00033     nodes = SG_MALLOC(FibonacciHeapNode* , max_num_nodes);
00034     for(int32_t i = 0; i < max_num_nodes; i++)
00035     {
00036         nodes[i] = new FibonacciHeapNode;
00037         clear_node(i);
00038     }
00039 
00040     Dn = 1 + (int32_t)(CMath::log2(max_num_nodes));
00041     A = SG_MALLOC(FibonacciHeapNode* , Dn);
00042     for(int32_t i = 0; i < Dn; i++)
00043     {
00044         A[i] = NULL;
00045     }
00046 
00047     num_nodes = 0;
00048     num_trees = 0;
00049 }
00050 
00051 CFibonacciHeap::~CFibonacciHeap()
00052 {
00053     for(int32_t i = 0; i < max_num_nodes; i++)
00054     {
00055         if(nodes[i] != NULL)
00056             delete nodes[i];
00057     }
00058     SG_FREE(nodes);
00059     SG_FREE(A);
00060 }
00061 
00062 void CFibonacciHeap::insert(int32_t index, float64_t key)
00063 {
00064     if(index >= max_num_nodes || index < 0)
00065         return;
00066 
00067     if(nodes[index]->index != -1)
00068         return; // node is not empty
00069 
00070     // init "new" node in array
00071     nodes[index]->child = NULL;
00072     nodes[index]->parent = NULL;
00073 
00074     nodes[index]->rank = 0;
00075     nodes[index]->index = index;
00076     nodes[index]->key = key;
00077     nodes[index]->marked = false;
00078 
00079     add_to_roots(nodes[index]);
00080     num_nodes++;
00081 }
00082 
00083 int32_t CFibonacciHeap::extract_min(float64_t &ret_key)
00084 {
00085     FibonacciHeapNode *min_node;
00086     FibonacciHeapNode *child, *next_child;
00087 
00088     int32_t result;
00089 
00090     if(num_nodes == 0)
00091         return -1;
00092 
00093     min_node = min_root;
00094     if(min_node == NULL)
00095         return -1; // heap is empty now
00096 
00097     child = min_node->child;
00098     while(child != NULL && child->parent != NULL)
00099     {
00100         next_child = child->right;
00101 
00102         // delete current child from childs list
00103         child->left->right = child->right;
00104         child->right->left = child->left;
00105 
00106         add_to_roots(child);
00107 
00108         // next iteration
00109         child = next_child;
00110     }
00111 
00112     // delete minimun from root list
00113     min_node->left->right = min_node->right;
00114     min_node->right->left = min_node->left;
00115 
00116     num_trees--;
00117 
00118     if(min_node == min_node->right)
00119     {
00120         min_root = NULL; // remove last element
00121     }
00122     else
00123     {
00124         min_root = min_node->right;
00125         consolidate();
00126     }
00127 
00128     result = min_node->index;
00129     ret_key = min_node->key;
00130     clear_node(result);
00131 
00132     num_nodes--;
00133 
00134     return result;
00135 }
00136 
00137 void CFibonacciHeap::clear()
00138 {
00139     min_root = NULL;
00140 
00141     // clear all nodes
00142     for(int32_t i = 0; i < max_num_nodes; i++)
00143     {
00144         clear_node(i);
00145     }
00146 
00147     num_nodes = 0;
00148     num_trees = 0;
00149 }
00150 
00151 int32_t CFibonacciHeap::get_key(int32_t index, float64_t &ret_key)
00152 {
00153     if(index >= max_num_nodes || index < 0)
00154         return -1;
00155     if(nodes[index]->index == -1)
00156         return -1;
00157 
00158     int32_t result = nodes[index]->index;
00159     ret_key = nodes[index]->key;
00160 
00161     return result;
00162 }
00163 
00164 void CFibonacciHeap::decrease_key(int32_t index, float64_t key)
00165 {
00166     FibonacciHeapNode* parent;
00167 
00168     if(index >= max_num_nodes || index < 0)
00169         return;
00170     if(nodes[index]->index == -1)
00171         return; // node is empty
00172     if(key > nodes[index]->key)
00173         return;
00174 
00175 
00176     nodes[index]->key = key;
00177 
00178     parent = nodes[index]->parent;
00179 
00180     if(parent != NULL && nodes[index]->key < parent->key)
00181     {
00182         cut(nodes[index], parent);
00183         cascading_cut(parent);
00184     }
00185 
00186     if(nodes[index]->key < min_root->key)
00187         min_root = nodes[index];
00188 }
00189 
00190 
00191 void CFibonacciHeap::add_to_roots(FibonacciHeapNode *up_node)
00192 {
00193     if(min_root == NULL)
00194     {
00195         // if heap is empty, node becomes circular root list
00196         min_root = up_node;
00197 
00198         up_node->left = up_node;
00199         up_node->right = up_node;
00200     }
00201     else
00202     {
00203         // insert node to root list
00204         up_node->right = min_root->right;
00205         up_node->left = min_root;
00206 
00207         up_node->left->right = up_node;
00208         up_node->right->left = up_node;
00209 
00210         // nomination of new minimum node
00211         if(up_node->key < min_root->key)
00212         {
00213             min_root = up_node;
00214         }
00215     }
00216 
00217     up_node->parent = NULL;
00218     num_trees++;
00219 }
00220 
00221 void CFibonacciHeap::consolidate()
00222 {
00223     FibonacciHeapNode *x, *y, *w;
00224     int32_t d;
00225 
00226     for(int32_t i = 0; i < Dn; i++)
00227     {
00228         A[i] = NULL;
00229     }
00230 
00231     min_root->left->right = NULL;
00232     min_root->left = NULL;
00233     w = min_root;
00234 
00235     do
00236     {
00237         x = w;
00238         d = x->rank;
00239         w = w->right;
00240 
00241         while(A[d] != NULL)
00242         {
00243             y = A[d];
00244 
00245             if(y->key < x->key)
00246             {
00247                 FibonacciHeapNode *temp;
00248 
00249                 temp = y;
00250                 y = x;
00251                 x = temp;
00252             }
00253 
00254             link_nodes(y, x);
00255 
00256             A[d] = NULL;
00257             d++;
00258         }
00259         A[d] = x;
00260     }
00261     while(w != NULL);
00262 
00263     min_root = NULL;
00264     num_trees = 0;
00265 
00266     for(int32_t i = 0; i < Dn; i++)
00267     {
00268         if(A[i] != NULL)
00269         {
00270             A[i]->marked = false;
00271             add_to_roots(A[i]);
00272         }
00273     }
00274 }
00275 
00276 void CFibonacciHeap::link_nodes(FibonacciHeapNode *y, FibonacciHeapNode *x)
00277 {
00278     if(y->right != NULL)
00279         y->right->left = y->left;
00280     if(y->left != NULL)
00281         y->left->right = y->right;
00282 
00283     num_trees--;
00284 
00285     y->left = y;
00286     y->right = y;
00287 
00288     y->parent = x;
00289 
00290     if(x->child == NULL)
00291     {
00292         x->child = y;
00293     }
00294     else
00295     {
00296         y->left = x->child;
00297         y->right = x->child->right;
00298 
00299         x->child->right = y;
00300         y->right->left = y;
00301     }
00302 
00303     x->rank++;
00304 
00305     y->marked = false;
00306 }
00307 
00308 void CFibonacciHeap::clear_node(int32_t index)
00309 {
00310     nodes[index]->parent = NULL;
00311     nodes[index]->child = NULL;
00312     nodes[index]->left = NULL;
00313     nodes[index]->right = NULL;
00314 
00315     nodes[index]->rank = 0;
00316     nodes[index]->index = -1;
00317     nodes[index]->key = 0;
00318 
00319     nodes[index]->marked = false;
00320 }
00321 
00322 void CFibonacciHeap::cut(FibonacciHeapNode *child, FibonacciHeapNode *parent)
00323 {
00324     if(parent->child == child)
00325         parent->child = child->right;
00326 
00327     if(parent->child == child)
00328         parent->child = NULL;
00329 
00330     parent->rank--;
00331 
00332     child->left->right = child->right;
00333     child->right->left = child->left;
00334     child->marked = false;
00335 
00336     add_to_roots(child);
00337 }
00338 
00339 void CFibonacciHeap::cascading_cut(FibonacciHeapNode *tree)
00340 {
00341     FibonacciHeapNode *temp;
00342 
00343     temp = tree->parent;
00344     if(temp != NULL)
00345     {
00346         if(!tree->marked)
00347         {
00348             tree->marked = true;
00349         }
00350         else
00351         {
00352             cut(tree, temp);
00353             cascading_cut(temp);
00354         }
00355     }
00356 }
00357 
00358 void CFibonacciHeap::debug_print()
00359 {
00360     SG_SPRINT("%d %d\n", num_trees, num_nodes);
00361     for(int32_t i = 0; i < max_num_nodes; i++)
00362     {
00363         if(nodes[i]->index == -1)
00364         {
00365             SG_SPRINT("None\n");
00366         }
00367         else
00368         {
00369             SG_SPRINT("%f\n",nodes[i]->key);
00370         }
00371     }
00372 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

SHOGUN Machine Learning Toolbox - Documentation