vektor.h

大型复杂网络社区划分的快速算法

////////////////////////////////////////////////////////////////////////
// --- COPYRIGHT NOTICE ---------------------------------------------
// FastCommunityMH - infers community structure of networks
// Copyright (C) 2004 Aaron Clauset
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
// 
// See http://www.gnu.org/licenses/gpl.txt for more details.
// 
////////////////////////////////////////////////////////////////////////
// Author       : Aaron Clauset  ([e-mail])				//
// Location     : U. Michigan, U. New Mexico						//
// Time         : January-August 2004							//
// Collaborators: Dr. Cris Moore ([e-mail])				//
//              : Dr. Mark Newman ([e-mail])				//
////////////////////////////////////////////////////////////////////////

#if !defined(vektor_INCLUDED)
#define vektor_INCLUDED

#include <iostream.h>

#if !defined(vektor_INCLUDED)
#define vektor_INCLUDED
#include "maxheap.h"
#endif

#if !defined(DPAIR_INCLUDED)
#define DPAIR_INCLUDED
class dpair {
public:
	int x; double y; dpair *next;
	dpair(); ~dpair();
};
dpair::dpair()  { x = 0; y = 0.0; next = NULL; }
dpair::~dpair() {}
#endif
struct dppair { dpair *head; dpair *tail; };

class element {
public:
	int		key;					// binary-tree key
	double    stored;				// additional stored value (associated with key)
	tuple	*heap_ptr;			// pointer to element's location in vektor max-heap
	
	bool		color;				// F: BLACK
								// T: RED
	element   *parent;				// pointer to parent node
	element   *left;				// pointer for left subtree
	element   *right;				// pointer for right subtree
	
	element(); ~element();
};
element::element()  {    key = 0; stored = -4294967296.0; color = false;
					parent  = NULL; left  = NULL; right  = NULL; }
element::~element() {}

/*   This vector implementation is a pair of linked data structures: a red-black balanced binary
	tree data structure and a maximum heap. This pair allows us to find a stored element in time
	O(log n), find the maximum element in time O(1), update the maximum element in time O(log n),
	delete an element in time O(log n), and insert an element in time O(log n). These complexities
	allow a much faster implementation of the fastCommunity algorithm. If we dispense with the
	max-heap, then some operations related to updating the maximum stored value can take up to O(n),
	which is potentially very slow.

	Both the red-black balanced binary tree and the max-heap implementations are custom-jobs. Note
	that the key=0 is assumed to be a special value, and thus you cannot insert such an item. 
	Beware of this limitation.
*/

class vektor {
private:
	element    *root;				// binary tree root
	element    *leaf;				// all leaf nodes
	maxheap    *heap;				// max-heap of elements in vektor
	int		 support;				// number of nodes in the tree

	void		rotateLeft(element *x);						// left-rotation operator
	void		rotateRight(element *y);						// right-rotation operator
	void		insertCleanup(element *z);					// house-keeping after insertion
	void		deleteCleanup(element *x);					// house-keeping after deletion
	dppair    *consSubtree(element *z);					// internal recursive cons'ing function
	dpair	*returnSubtreeAsList(element *z, dpair *head);
	void		printSubTree(element *z);					// display the subtree rooted at z
	void		deleteSubTree(element *z);					// delete subtree rooted at z
	element   *returnMinKey(element *z);					// returns minimum of subtree rooted at z
	element   *returnSuccessor(element *z);					// returns successor of z's key
	
public:
	vektor(int size); ~vektor();							// default constructor/destructor

	element*  findItem(const int searchKey);				// returns T if searchKey found, and
													// points foundNode at the corresponding node
	void		insertItem(int newKey, double newStored);		// insert a new key with stored value
	void		deleteItem(int killKey);						// selete a node with given key
	void		deleteTree();								// delete the entire tree
	dpair	*returnTreeAsList();						// return the tree as a list of dpairs
	dpair	*returnTreeAsList2();						// return the tree as a list of dpairs
	tuple	returnMaxKey();							// returns the maximum key in the tree
	tuple	returnMaxStored();							// returns a tuple of the maximum (key, .stored)
	int		returnNodecount();							// returns number of items in tree

	void		printTree();								// displays tree (in-order traversal)
	void		printHeap();								// displays heap
	int		returnArraysize();							// 
	int		returnHeaplimit();							// 

};

// ------------------------------------------------------------------------------------
// Red-Black Tree methods

vektor::vektor(int size) {
	root = new element;
	leaf = new element;
	heap = new maxheap(size);

	leaf->parent   = root;

	root->left	= leaf;
	root->right    = leaf;
	support		= 0;
}

vektor::~vektor() {
	if (root != NULL && (root->left != leaf || root->right != leaf)) { deleteSubTree(root); }
	support         = 0;
	delete leaf;
	root		= NULL;
	leaf		= NULL;
	delete heap;
	heap		= NULL;
}

void vektor::deleteTree() { if (root != NULL) { deleteSubTree(root); } return; }

void vektor::deleteSubTree(element *z) {

	if (z->left  != leaf) { deleteSubTree(z->left);  }
	if (z->right != leaf) { deleteSubTree(z->right); }
	delete z;
	z = NULL;
	return;
}


// Search Functions -------------------------------------------------------------------

// public search function - if there exists a element in the three with key=searchKey,
// it returns TRUE and foundNode is set to point to the found node; otherwise, it sets
// foundNode=NULL and returns FALSE
element* vektor::findItem(const int searchKey) {

	element *current;    current = root;
	if (current->key==0) { return NULL; }							// empty tree; bail out
	while (current != leaf) {
		if (searchKey < current->key) {							// left-or-right?
			if (current->left  != leaf) { current = current->left;  }	// try moving down-left
			else { return NULL; }								//   failure; bail out
		} else {												// 
			if (searchKey > current->key) {							// left-or-right?
				if (current->right  != leaf) { current = current->right;  }	// try moving down-left
				else { return NULL; }							//   failure; bail out
			} else { return current; }							// found (searchKey==current->key)
		}
	}
	return NULL;
}

// Return Item Functions -------------------------------------------------------------------
// public function which returns the tree, via pre-order traversal, as a linked list

dpair* vektor::returnTreeAsList() { // pre-order traversal
	
	dpair  *head, *tail;

	head    = new dpair;
	head->x = root->key;
	head->y = root->stored;
	tail = head;

	if (root->left  != leaf) { tail = returnSubtreeAsList(root->left,  tail); }
	if (root->right != leaf) { tail = returnSubtreeAsList(root->right, tail); }
	
	if (head->x==0) { return NULL; /* empty tree */} else { return head; }
}

dpair* vektor::returnSubtreeAsList(element *z, dpair *head) {
	dpair *newnode, *tail;
	
	newnode    = new dpair;
	newnode->x = z->key;
	newnode->y = z->stored;
	head->next = newnode;
	tail       = newnode;
	
	if (z->left  != leaf) { tail = returnSubtreeAsList(z->left,  tail); }
	if (z->right != leaf) { tail = returnSubtreeAsList(z->right, tail); }
	
	return tail;
}

tuple vektor::returnMaxStored() { return heap->returnMaximum(); }

tuple vektor::returnMaxKey() {
	tuple themax;
	element *current;
	current = root;
	while (current->right != leaf) {		// search to bottom-right corner of tree
		current = current->right; }		// 
	themax.m = current->stored;			// store the data found
	themax.i = current->key;				// 
	themax.j = current->key;				// 
	
	return themax;						// return that data
}

// private functions for deleteItem() (although these could easily be made public, I suppose)
element* vektor::returnMinKey(element *z) {
	element *current;

	current = z;
	while (current->left != leaf) {		// search to bottom-right corner of tree
		current = current->left; }		// 
	return current;					// return pointer to the minimum
}

element* vektor::returnSuccessor(element *z) {
	element *current, *w;
	
	w = z;
	if (w->right != leaf) {				// if right-subtree exists, return min of it
		return returnMinKey(w->right); }
	current = w->parent;				// else search up in tree
	while ((current!=NULL) && (w==current->right)) {
		w       = current;
		current = current->parent;		// move up in tree until find a non-right-child
	}
	return current;
}

int vektor::returnNodecount() { return support; }
int vektor::returnArraysize() { return heap->returnArraysize(); }
int vektor::returnHeaplimit() { return heap->returnHeaplimit(); }

// Heapification Functions -------------------------------------------------------------------

// Insert Functions -------------------------------------------------------------------
// public insert function
void vektor::insertItem(int newKey, double newStored) {
	
	// first we check to see if newKey is already present in the tree; if so, we simply
	// set .stored += newStored; if not, we must find where to insert the key
	element *newNode, *current;
	bool foundFlag;

	current = findItem(newKey);						// find newKey in tree; return pointer to it O(log k)
	if (current != NULL) {
		current->stored += newStored;					// update its stored value
		heap->updateItem(current->heap_ptr, current->stored);
												// update corresponding element in heap + reheapify; O(log k)
	} else {										// didn't find it, so need to create it
		tuple newitem;								// 
		newitem.m = newStored;						//  
		newitem.i = -1;							//  
		newitem.j = newKey;							//