fheap.cpp

I implement Dijkstra s Single Source Shortest Path, say SSP, algorithm for directed graphs using a s

#include "FHeap.h"

FHeap::FHeap(int size)
: degreeList(NULL)
{
	maxSize = size; 
	initial();
}

FHeap::~FHeap(void)
{
	if(maxDegree>0){
		delete [] allNodes;
		delete [] degreeList;
	}
}

void FHeap::initial()
{
	maxDegree = 0;
	if(maxSize!=0){
		allNodes = new FHeapNode * [maxSize];
		for(int i=0; i<maxSize; i++){
			allNodes[i] = new FHeapNode();
		}
		maxDegree = 1 + (int)(1.44 * log(float(maxSize))/log(2.0));
		degreeList = new int [maxDegree];
	}

	currentSize = 0;
	min = 0;
	tree_num = 0;
}

/*
 *Insert a new element (node, dist) into the current min FHeap.
 *the new min element will be the smaller one of the original min and newNode.
 *int node: the ID of the new node;
 *int dist: the distance from source to node
 *if node is already existed, return -1
 *else, return the current size of PHeap after insert.
 */
int FHeap::insert(int node, int dist){
	//cout<<"insert ("<<node<<", "<<dist<<")"<<endl;
	FHeapNode * newNode = allNodes[node];
	newNode->child = 0;
	newNode->chlidcut = false;
	newNode->degree = 0;
	newNode->node = node;
	newNode->dist = dist;
	newNode->parent = 0;
	newNode->left = newNode;
	newNode->right = newNode;

	//allNodes[node] = newNode;
	//add new node into the top level of the heap
	
	if(currentSize>0)
	{
		meld(newNode, 1);
	}
	else{
		min = newNode;
		tree_num=1;
	}
	return ++currentSize;
}

/*
 *Delete current min element from PHeap and then reconstruct the FHeap using 
 *pairwise combine
 *return the node of the min element
 */
int FHeap::deleteMin()
{
	//cout<<"delete min"<<endl;
	int node = min->node;
	if(--currentSize==0){
		delete min;
		tree_num--;
		allNodes[node] = 0;
		return node;
	}

	//cut the chldren off from current min and find the min child of current min to form a new FHeap
	FHeapNode * minChild = min->child;
	FHeapNode * curChild = min->child;
	int addTreeNum = min->degree;
	for(int i=0; i<min->degree; i++){
		curChild->parent = 0;
		curChild->chlidcut = false;
		if(curChild->dist < minChild->dist){
			minChild = curChild;
		}
		curChild = curChild->right;
	}

	if(--tree_num==0){
		delete min;
		tree_num = addTreeNum;
		allNodes[node] = 0;
		min = minChild;
		return node;
	}

	//kick off current min and find next min in current top level list;
	

	for(int i1=0; i1<currentSize; i1++){ min = min->right->left;}
	min->left->right = min->right;
	min->right->left = min->left;

	FHeapNode * newMin = min->right;

	FHeapNode * stop = newMin;
	FHeapNode * now = stop->right;
	while(now!=stop){
		if(newMin->dist > now->dist){
			newMin = now;
		}
		now = now->right;
	}
	delete min;
	min = newMin;
	
	//meld current FHeap with the children of old min;
	//cout<<"min:"<<min->node<<"Tree:"<<tree_num<<endl;
	if(addTreeNum!=0)
		meld(minChild, addTreeNum);
	//cout<<"min:"<<min->node<<"Tree:"<<tree_num<<endl;

	if(tree_num>=1)
		pairwiseCombine();

	//cout<<"min:"<<min->node<<"Tree:"<<tree_num<<endl;
	allNodes[node] = 0;
	return node;
}

/*
 *Pairwise combine the min trees in the top level list of current FHeap
 */
void FHeap::pairwiseCombine()
{
	for(int i=0; i<maxDegree; i++){
		degreeList[i] = -1;
	}

	FHeapNode * stop = min;
	FHeapNode * now = min;
	do{
		FHeapNode * next = now->right;
		int d = now->degree;
		if(degreeList[d]!=-1){
			combineTrees(now, allNodes[degreeList[d]]);
		}
		else{
			degreeList[d] = now->node;
		}

		now = next;
	}
	while(now!=stop);
}

/*
 *Meld a new FHeap whose min element at newNode into the current FHeap.
 *After meld, the new min element will be the smaller one of the current min and newNode.
 *FHeapNode * newNode: the min element of the new PHeap that need to be melded
 *int addTree: the number of min heaps in the FHeap about to add. 
 */
void FHeap::meld(FHeapNode * newNode, int addTree)
{
	FHeapNode * origin_right = min->right;
	FHeapNode * new_right = newNode->left;
	min->right = newNode;
	newNode->left = min;
	origin_right->left = new_right;
	new_right->right = origin_right;

	if(newNode->dist < min->dist) {
		min = newNode;
	}

	tree_num += addTree;
}

void FHeap::combineTrees(FHeapNode * tree1, FHeapNode * tree2)
{
	FHeapNode * big = (tree1->dist > tree2->dist) ? tree1 : tree2;
	FHeapNode * small = (tree1->dist <= tree2->dist) ? tree1 : tree2;
	if(big==min){
		FHeapNode * tmp = small;
		small = min;
		big = tmp;
	}

	//slice big out of the top level list
	big->right->left = big->left;
	big->left->right = big->right;
	tree_num--;

	//add big as a child of small
	big->parent = small;
	big->chlidcut = false;
	degreeList[small->degree] = -1;
	small->degree++;

	if(small->degree==1){
		small->child = big;
		big->right = big;
		big->left = big;
	}
	else{	
		FHeapNode * c = small->child;
		big->right = c->right;
		big->left = c;
		c->right->left = big;
		c->right = big;
	}
	
	if(degreeList[small->degree]!=-1)
	{
		combineTrees(small, allNodes[degreeList[small->degree]]);
	}
	else{
		degreeList[small->degree] = small->node;
	}
}

/*
 *Decrease the dist of a certain node, then reconstruct the FHeap using pairwise combine if needed
 *int node: the node to decrease value.
 *int newDist: new value of the dist of the node
 */
int FHeap::decreasDist(int node, int newDist)
{
	FHeapNode * theNode = allNodes[node];
	if(theNode==0){
		cout<<"Node "<<node<<" does not exist!"<<endl;
		return -1;
	}

	theNode->dist = newDist;
	FHeapNode * parent = theNode->parent;

	//if theNode is smaller than its parents, remove it and add it to the top level list
	if(parent!=0&&theNode->dist<parent->dist){
		cut(theNode, parent);
		cascadingCut(parent);
	}

	if(min->dist>theNode->dist) min = theNode;
	return 0;
}
/*
 *perform the cascading cut operation start from the augment node
 */
void FHeap::cascadingCut(FHeapNode * node)
{
	FHeapNode * p = node->parent;
	if(p!=0){
		if(node->chlidcut = false)
		{
			node->chlidcut = true;
		}
		else{
			cut(node, p);
			cascadingCut(p);
		}
	}
}

/*
 *cut the node from its sibling list and reinsert into the top level list
 */
void FHeap::cut(FHeapNode * theNode, FHeapNode * parent)
{
	(parent->degree)--;
	if(parent->degree==0){
		parent->child = 0;
	}
	else if(parent->child==theNode){
		parent->child = theNode->left;
	}

	theNode->left->right = theNode->right;
	theNode->right->left = theNode->left;
	theNode->right = theNode;
	theNode->left = theNode;
	theNode->parent = 0;
	theNode->chlidcut = false;
	meld(theNode, 1);
}

void FHeap::testFHeap(void)
{
	FHeap * f = new FHeap(20);
	f->insert(0, 1);
	cout<<"min node: "<<f->min->node<<" dist:"<<f->min->dist<<endl;
	f->insert(-1, 0);
	cout<<"min node: "<<f->min->node<<" dist:"<<f->min->dist<<endl;
	f->insert(2, 4);
	cout<<"min node: "<<f->min->node<<" dist:"<<f->min->dist<<endl;
	f->insert(3, 5);
	f->insert(4, 6);
	cout<<"min node: "<<f->min->node<<" dist:"<<f->min->dist<<endl;
	f->deleteMin();
	cout<<"min node: "<<f->min->node<<" dist:"<<f->min->dist<<endl;
	f->insert(7, 9);
	f->insert(10, 2);
	FHeap * f1 = new FHeap(20);
	f1->insert(12, 20);
	f1->insert(16, 19);
	
/*	f1->insert(-1, -1);
	f1->deleteMin();
	f->meld(f1);
	f->currentSize += f1->currentSize;
	cout<<"min node: "<<f->min->node<<" dist:"<<f->min->dist<<endl;
	FHeap * f2 = new FHeap(20);
	f2->insert(5, 7);
	f2->insert(9, 11);
	f2->insert(-1, -1);
	f2->deleteMin();
	f->meld(f2);
	f->currentSize += f2->currentSize;
	cout<<"min node: "<<f->min->node<<" dist:"<<f->min->dist<<endl;
	f->deleteMin();
	cout<<"min node: "<<f->min->node<<" dist:"<<f->min->dist<<endl;

	FHeapNode * fn = new FHeapNoe();
	fn->dist = 9;
	fn->node = 1;
	f->min->*/
}