Something went wrong. Try again.
Distances on Directed Graphs in R
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459/* File fheap.c - Fibonacci Heap * ---------------------------------------------------------------------------- * Mark Padgham, adapted from code by Shane Saunders */#include <cmath>#if defined(FHEAP_DUMP) && FHEAP_DUMP > 0#include <cstdio>#endif#include "fheap.h"
/*--- FHeap (public methods) ------------------------------------------------*/
/* --- Constructor --- * Creates an FHeap object capable of holding up to $n$ items. */FHeap::FHeap(size_t n){#if FHEAP_DUMP Rcpp::Rcout << "new, ";#endif maxTrees = 1 + static_cast <size_t>(1.44 * log(static_cast <double> (n)) / log (2.0)); maxNodes = n;
trees = new FHeapNode *[maxTrees]; for(size_t i = 0; i < maxTrees; i++) trees[i] = nullptr;
nodes = new FHeapNode *[n]; for(size_t i = 0; i < n; i++) nodes[i] = nullptr;
itemCount = 0;
/* The $treeSum$ of the heap helps to keep track of the maximum rank while * nodes are inserted or deleted. */ treeSum = 0;
/* For experimental purposes, we keep a count of the number of key * comparisons. */ compCount = 0;
#if FHEAP_DUMP Rcpp::Rcout << "new-exited, ";#endif}
/* --- Destructor ---*/FHeap::~FHeap(){#if FHEAP_DUMP Rcpp::Rcout << "delete, ";#endif
for(size_t i = 0; i < maxNodes; i++) delete nodes[i]; delete [] nodes; delete [] trees;
#if FHEAP_DUMP Rcpp::Rcout << "delete-exited, ";#endif}
/* --- insert() --- * Inserts an item $item$ with associated key $k$ into the heap. */void FHeap::insert(size_t item, double k){ FHeapNode *newNode;
#if FHEAP_DUMP Rcpp::Rcout << "insert, ";#endif
/* create an initialise the new node */ newNode = new FHeapNode; newNode->child = nullptr; newNode->left = newNode->right = newNode; newNode->rank = 0; newNode->item = item; newNode->key = k;
/* maintain a pointer to $item$'s new node in the heap */ nodes[item] = newNode;
/* meld the new node into the heap */ meld(newNode);
/* update the heaps node count */ itemCount++;
#if FHEAP_DUMP Rcpp::Rcout << "insert-exited, ";#endif}
/* --- deleteMin() --- * Deletes and returns the minimum item from the heap. */size_t FHeap::deleteMin(){ FHeapNode *minNode, *child, *next; double k, k2; size_t r, v, item;
#if FHEAP_DUMP Rcpp::Rcout << "deleteMin, ";#endif
/* First we determine the maximum rank in the heap. */ v = treeSum; // MP Note: r was an int formerly intialised at -1, but it's used as a // direct array index below, so really should be unsigned! The r-- at end // fixes that. r = 0; while(v) { v = v >> 1; r++; } r--;
/* Now determine which root node is the minimum. */ minNode = trees[r]; k = minNode->key; while(r > 0) { r--; next = trees[r]; if(next) { if((k2 = next->key) < k) { k = k2; minNode = next; } compCount++; } }
/* We remove the minimum node from the heap but keep a pointer to it. */ r = minNode->rank; trees[r] = nullptr; treeSum -= (1 << r);
child = minNode->child; if(child) meld(child);
/* Record the vertex no of the old minimum node before deleting it. */ item = minNode->item; nodes[item] = nullptr; delete minNode; itemCount--;
#if FHEAP_DUMP Rcpp::Rcout << "deleteMin-exited, ";#endif
return item;}
/* --- decreaseKey() --- * Decreases the key used for item $item$ to the value newValue. It is left * for the user to ensure that newValue is in-fact less than the current value */void FHeap::decreaseKey(size_t item, double newValue){ FHeapNode *cutNode, *parent, *newRoots, *r, *l; size_t prevRank;
#if FHEAP_DUMP Rcpp::Rcout << "decreaseKey on vn = " << item << ", ";#endif
/* Obtain a pointer to the decreased node and its parent then decrease the * nodes key. */ cutNode = nodes[item]; parent = cutNode->parent; cutNode->key = newValue;
/* No reinsertion occurs if the node changed was a root. */ if(!parent) {#if FHEAP_DUMP Rcpp::Rcout << "decreaseKey-exited, ";#endif return; }
/* Update the left and right pointers of cutNode and its two neighbouring * nodes. */ l = cutNode->left; r = cutNode->right; l->right = r; r->left = l; cutNode->left = cutNode->right = cutNode;
/* Initially the list of new roots contains only one node. */ newRoots = cutNode;
/* While there is a parent node that is marked a cascading cut occurs. */ while(parent && parent->marked) {
/* Decrease the rank of cutNode's parent and update its child pointer. */ parent->rank--; if(parent->rank) { if(parent->child == cutNode) parent->child = r; } else { parent->child = nullptr; }
/* Update the cutNode and parent pointers to the parent. */ cutNode = parent; parent = cutNode->parent;
/* Update the left and right pointers of cutNodes two neighbouring * nodes. */ l = cutNode->left; r = cutNode->right; l->right = r; r->left = l;
/* Add cutNode to the list of nodes to be reinserted as new roots. */ l = newRoots->left; newRoots->left = l->right = cutNode; cutNode->left = l; cutNode->right = newRoots; newRoots = cutNode; }
/* If the root node is being relocated then update the trees[] array. * Otherwise mark the parent of the last node cut. */ if(!parent) { prevRank = cutNode->rank + 1; trees[prevRank] = nullptr; treeSum -= (1 << prevRank); } else { /* Decrease the rank of cutNode's parent an update its child pointer. */ parent->rank--; if(parent->rank) { if(parent->child == cutNode) parent->child = r; } else { parent->child = nullptr; }
parent->marked = 1; }
/* Meld the new roots into the heap. */ meld(newRoots);
#if FHEAP_DUMP Rcpp::Rcout << "decreaseKey-exited, ";#endif}
/*--- FHeap (private methods) -----------------------------------------------*/
/* --- meld() --- * melds the linked list of trees pointed to by $treeList$ into the heap. */void FHeap::meld(FHeapNode *treeList){ FHeapNode *first, *next, *nodePtr, *newRoot, *temp, *temp2, *lc, *rc; size_t r;
#if FHEAP_DUMP Rcpp::Rcout << "meld: ";#endif
/* We meld each tree in the circularly linked list back into the root level * of the heap. Each node in the linked list is the root node of a tree. * The circularly linked list uses the sibling pointers of nodes. This * makes melding of the child nodes from a deleteMin operation simple. */ nodePtr = first = treeList;
do {
#if FHEAP_DUMP Rcpp::Rcout << nodePtr->item << ", ";#endif
/* Keep a pointer to the next node and remove sibling and parent links * from the current node. nodePtr points to the current node. */ next = nodePtr->right; nodePtr->right = nodePtr->left = nodePtr; nodePtr->parent = nullptr;
/* We merge the current node, nodePtr, by inserting it into the * root level of the heap. */ newRoot = nodePtr; r = nodePtr->rank;
/* This loop inserts the new root into the heap, possibly restructuring * the heap to ensure that only one tree for each degree exists. */ do {
/* Check if there is already a tree of degree r in the heap. * If there is then we need to link it with newRoot so it will be * reinserted into a new place in the heap. */ if((temp = trees[r])) {
/* temp will be linked to newRoot and relocated so we no * longer will have a tree of degree r. */ trees[r] = nullptr; treeSum -= (1 << r);
/* Swap temp and newRoot if necessary so that newRoot always * points to the root node which has the smaller key of the * two. */ if(temp->key < newRoot->key) { temp2 = newRoot; newRoot = temp; temp = temp2; } compCount++;
/* Link temp with newRoot, making sure that sibling pointers * get updated if rank is greater than 0. Also, increase r for * the next pass through the loop since the rank of new has * increased. */ if(r++ > 0) { rc = newRoot->child; lc = rc->left; temp->left = lc; temp->right = rc; lc->right = rc->left = temp; } newRoot->child = temp; newRoot->rank = r; temp->parent = newRoot; temp->marked = 0; } /* Otherwise if there is not a tree of degree r in the heap we * allow newRoot, which possibly carries moved trees in the heap, * to be a tree of degree r in the heap. */ else {
trees[r] = newRoot; treeSum += (1 << r);
/* NOTE: Because newRoot is now a root we ensure it is * marked. */ newRoot->marked = 1; }
/* Note that temp will be NULL if and only if there was not a tree * of degree r. */ } while(temp);
nodePtr = next;
} while(nodePtr != first);
#if FHEAP_DUMP Rcpp::Rcout << "meld-exited, ";#endif}
/*--- FHeap (debugging) -----------------------------------------------------*/
/* --- dumpNodes() --- * Recursively print a text representation of the node subtree starting at the * node poined to by $node$, using an indentationlevel of $level$. */void FHeap::dumpNodes(FHeapNode *node, size_t level){ (void) node; (void) level;#if FHEAP_DUMP FHeapNode *childNode, *partner; size_t childCount;
/* Print leading whitespace for this level. */ for(size_t i = 0; i < level; i++) Rcpp::Rcout << " ";
Rcpp::Rcout << node->item << "(" << node->key << ")[" << node->rank << "]" << std::endl;
if((childNode = node->child)) { childNode = node->child->right;
childCount = 0;
do { dumpNodes(childNode, level+1); if(childNode->dim > node->dim) { for(size_t i = 0; i < level+1; i++) Rcpp::Rcout << " "; throw std::runtime_error ("error(dim)"); } if(childNode->parent != node) { for(size_t i = 0; i < level+1; i++) Rcpp::Rcout << " "; throw std::runtime_error ("error(parent)"); } childNode = childNode->right; childCount++; } while(childNode != node->child->right);
if(childCount != node->dim) { for(size_t i = 0; i < level; i++) Rcpp::Rcout << " "; throw std::runtime_error ("error(childCount)"); } } else { if(node->dim != 0) { for(size_t i = 0; i < level; i++) Rcpp::Rcout << " "; throw std::runtime_error ("error(dim)"); } }#endif}
/* --- dump() --- * Print a text representation of the heap to the standard output. */void FHeap::dump() const{#if FHEAP_DUMP FHeapNode *node;
Rcpp::Rcout << std::endl; Rcpp::Rcout << "treeSum = " << treeSum << std::endl; Rcpp::Rcout << "array entries 0..maxTrees ="; for(size_t i = 0; i < maxTrees; i++) { bool tempval = trees [i] ? 1 : 0; Rcpp::Rcout << " " << tempval; } Rcpp::Rcout << std::endl << std::endl; for(size_t i = 0; i < maxTrees; i++) { if((node = trees[i])) { Rcpp::Rcout << "tree " << i; dumpNodes(node, 0); Rcpp::Rcout << std::endl; } } Rcpp::Rcout.flush ();#endif }
/*---------------------------------------------------------------------------*/