About Programming / Algorithms / haXe

Example of Coding on haXe (Quicksort, Hoarse, Random) – Part 6

In this example you will see: Regular quicksort, quicksort using random partition, quicksort using Hoarse partition, quicksort using random partition together with Hoarse partition

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

example_6.hx:

/**
 * @author: Alejandro G. Carlstein R. M.
 */

enum PartitionType{
	DEFAULT;
	RANDOMIZED;
	HOARSE;
	RANDOMIZED_HOARSE;
}

class QuickSort{
	private var data : Array<Int>;
	private var partition_type : PartitionType;

	private function _sort(start_index : Int, end_index : Int) : Void{
		if (start_index < end_index){
			var partition_index : Int = getPartitionIndex(start_index, end_index);
			_sort(start_index, partition_index - 1);
			_sort(partition_index + 1, end_index);
		}
	}

	private function getPartitionIndex(start_index : Int, end_index : Int) : Int{
		switch(partition_type){
			case DEFAULT:
				return partition(start_index, end_index);
			case RANDOMIZED:
				return randomPartition(start_index, end_index);
			case HOARSE:
				return hoarsePartition(start_index, end_index);
			case RANDOMIZED_HOARSE:
				return randomizedHoarsePartition(start_index, end_index);
		}
		return -1;
	}

	private function partition(start_index : Int, end_index : Int) : Int{
		var pivot_value : Int = data[end_index];
		var i : Int = start_index - 1;

		var index : Int = start_index;
		while (index < end_index){
			if (data[index] < pivot_value)
				exchange(++i, index);
			++index;
		}
		exchange(++i, end_index);
		return i;
	}

	private function randomPartition(start_index : Int, end_index : Int) : Int{
		exchange(getRandom(start_index, end_index), end_index);
		return partition(start_index, end_index);
	}

	private function getRandom(maximum_value : Int, minimum_value : Int) : Int{
		return Math.floor(Math.random() % (maximum_value - minimum_value)) + minimum_value;
	}

	private function hoarsePartition(start_index : Int, end_index : Int) : Int{
		var pivot_value : Int = data[start_index];
		var left_index : Int = start_index;
		var right_index : Int = end_index;
		while (left_index < right_index){
			while (data[left_index] < pivot_value)
				--right_index;
			while (data[left_index] > pivot_value)
				++left_index;
			if (left_index < right_index)
				exchange(left_index, right_index);
			else
				break;
			if (data[right_index] == data[left_index]){
				--right_index;
				++left_index;
			}
		}
		return right_index;
	}

	private function randomizedHoarsePartition(start_index : Int, end_index : Int) : Int{
		exchange(getRandom(start_index, end_index), end_index);
		return hoarsePartition(start_index, end_index);
	}	

	private function exchange(index_a : Int, index_b : Int) : Void{
		var temp_value : Int = data[index_a];
		data[index_a] = data[index_b];
		data[index_b] = temp_value;
	}

	// Constructor ( ? means that items is optional)
	public function new(?data : Array<Int>, ?partition_type : PartitionType){
		this.data = (data == null) ? new Array() : data;
		setPartitionType(partition_type);
	}

	public function getData() : Array<Int> {
		return data;
	}

	public function setData(data : Array<Int>) : Void {
		this.data = data;
	}

	public function sort() : Void{
		if(data.iterator().hasNext())
			_sort(0, data.length - 1);
	}

	public function setPartitionType(parition_type : PartitionType) : Void{
		this.partition_type = (partition_type == null) ? DEFAULT : partition_type;
	}

}

class Example_6 {

	static function main(){

		var data : Array<Int> = [3, 7, 1, -1];
		printData(data);

		trace('QuickSort using regular partition:');
		var quicksort = new QuickSort(data, DEFAULT);
		quicksort.sort();
		data = quicksort.getData();
		printData(data);		

		data = [3, 7, 1, -1];
		trace('QuickSort using randomized partition:');
		var quicksort_1 = new QuickSort(data, RANDOMIZED);
		quicksort_1.sort();
		data = quicksort_1.getData();
		printData(data);		

		data = [3, 7, 1, -1];
		trace('QuickSort using Hoarse partition:');
		var quicksort_2 = new QuickSort(data, HOARSE);
		quicksort_2.sort();
		data = quicksort_2.getData();
		printData(data);		

		data = [3, 7, 1, -1];
		trace('QuickSort using randomized Hoarse partition:');
		var quicksort_3 = new QuickSort(data, RANDOMIZED_HOARSE);
		quicksort_3.sort();
		data = quicksort_3.getData();
		printData(data);
	}

	private static function printData(data : Array<Int>){
		var iter = data.iterator();
		var index : Int = 0;
		trace('[DATA]');
		while (iter.hasNext()){
			trace('data[' + index++ + ']: ' + iter.next());
		}
	}

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment
About Programming / Algorithms / haXe

Example of Coding on haXe (Heapsort, Binary Search) – Part 5

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used.

In this example you will see: Binary search by using heapsort for sorting.

example_5.hx:

/**
 * @author: Alejandro G. Carlstein R. M.
 */

class HeapSort{

	private var data : Array<Int>;
	private var heap_size : Int;
	private inline function leftChild(index : Int) : Int{ return (index << 1) + 1;	}
	private inline function rightChild(index : Int) : Int{ return (index << 1) + 2; }

	// Constructor ( ? means that items is optional)
	public function new(?data : Array<Int>){
		this.data = (data == null) ? new Array() : data;
	}

	public function getData() : Array<Int> {
		return data;
	}

	public function setData(data : Array<Int>) : Void {
		this.data = data;
	}

	public function sort() : Void{
		if(data.iterator().hasNext()){
			heap_size = data.length;
			buildMaxHeap();
			var index : Int = data.length - 1;
			while (index > -1){
				exchange(0, index);
				maxHeapify(0, --heap_size);
				--index;
			}
		}else{
			trace('There is no data to sort');
		}
	}

	private function buildMaxHeap() : Void{
		var index : Int = data.length >> 1;
		while (index > -1){
			maxHeapify(index, heap_size);
			--index;
		}
	}

	private function maxHeapify(index : Int, heapSize : Int) : Void{
		var largest : Int = index;
		var left : Int = leftChild(index);
		var right : Int = rightChild(index);	

		if (left < heapSize && data[left] > data[index])
			largest = left;

		if (right < heapSize && data[right] > data[largest])
			largest = right;

		if (largest != index){
			exchange(index, largest);
			maxHeapify(largest, heapSize);
		}
	}

	private function exchange(index_a : Int, index_b : Int) : Void{
		var temp_value : Int = data[index_a];
		data[index_a] = data[index_b];
		data[index_b] = temp_value;
	}

}

class BinarySearch{
	private var heapsort : HeapSort;
	private var data : Array<Int>;
	private function search(value : Int, start_index : Int, end_index : Int){
		var middle_index : Int = (start_index + end_index) >> 1;
		var was_found : Bool = false;
		if(start_index < end_index){
			if(data[middle_index] == value){
				return true;
			}else{
				if(data[middle_index] > value){
					was_found = search(value, start_index, middle_index);
				}else{
					was_found = search(value, middle_index + 1, end_index);
				}
			}
		}
		return was_found;
	}

	// Constructor ( ? means that items is optional)
	public function new(?data : Array<Int>){
		this.data = (data == null) ? new Array() : data;
		if (data != null) setData(data);
	}

	public function getData() : Array<Int> {
		return data;
	}

	public function setData(data : Array<Int>) : Void {
		if (data != null){
			heapsort = new HeapSort();
			heapsort.setData(data);
			heapsort.sort();
			data = heapsort.getData();
		}
	}

	public function doExist(value : Int) : Bool{
		return search(value, 0, data.length);
	}

}

class Example_5 {

	static function main(){

		var data : Array<Int> = [3, 7, 5, -1, 6, 1, -3];
		printData(data);

		trace('Binary Search:');
		var binarySearch = new BinarySearch(data);
		trace ('Do 3 exist? ' + binarySearch.doExist(3));
		trace ('Do 4 exist? ' + binarySearch.doExist(4));
		trace ('Do 7 exist? ' + binarySearch.doExist(7));

		data = binarySearch.getData();
		printData(data);		

	}

	private static function printData(data : Array<Int>){
		var iter = data.iterator();
		var index : Int = 0;
		trace('[DATA]');
		while (iter.hasNext()){
			trace('data[' + index++ + ']: ' + iter.next());
		}
	}

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment
About Programming / Algorithms / haXe

Example of Coding on haXe (Heapsort) – Part 4

In this example you will see: Heapsort algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

example_4.hx:

/**
 * @author: Alejandro G. Carlstein R. M.
 */

class HeapSort{

	private var data : Array<Int>;
	private var heap_size : Int;
	private inline function leftChild(index : Int) : Int{ return (index << 1) + 1;	}
	private inline function rightChild(index : Int) : Int{ return (index << 1) + 2; }

	// Constructor ( ? means that items is optional)
	public function new(?data : Array<Int>){
		this.data = (data == null) ? new Array() : data;
	}

	public function getData() : Array<Int> {
		return data;
	}

	public function setData(data : Array<Int>) : Void {
		this.data = data;
	}

	public function sort() : Void{
		if(data.iterator().hasNext()){
			heap_size = data.length;
			buildMaxHeap();
			var index : Int = data.length - 1;
			while (index > -1){
				exchange(0, index);
				maxHeapify(0, --heap_size);
				--index;
			}
		}else{
			trace('There is no data to sort');
		}
	}

	private function buildMaxHeap() : Void{
		var index : Int = data.length >> 1;
		while (index > -1){
			maxHeapify(index, heap_size);
			--index;
		}
	}

	private function maxHeapify(index : Int, heapSize : Int) : Void{
		var largest : Int = index;
		var left : Int = leftChild(index);
		var right : Int = rightChild(index);	

		if (left < heapSize && data[left] > data[index])
			largest = left;

		if (right < heapSize && data[right] > data[largest])
			largest = right;

		if (largest != index){
			exchange(index, largest);
			maxHeapify(largest, heapSize);
		}
	}

	private function exchange(index_a : Int, index_b : Int) : Void{
		var temp_value : Int = data[index_a];
		data[index_a] = data[index_b];
		data[index_b] = temp_value;
	}

}

class Example_4 {

	static function main(){

		var data : Array<Int> = [3, 7, 5, -1, 6, 1];
		printData(data);

		trace('heapsort:');
		var heapsort = new HeapSort(data);
		trace('sorting...');
		heapsort.sort();
		data = heapsort.getData();
		printData(data);		

		data = [3, 7, 5, -1, 6, 1];
		printData(data);		

		trace('heapsort_2:');
		var heapsort_2 = new HeapSort();
		trace('sorting without data...');
		heapsort_2.sort();
		trace('sorting with data...');
		heapsort_2.setData(data);
 		heapsort_2.sort();
 		printData(data);

	}

	private static function printData(data : Array<Int>){
		var iter = data.iterator();
		var index : Int = 0;
		trace('[DATA]');
		while (iter.hasNext()){
			trace('data[' + index++ + ']: ' + iter.next());
		}
	}

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment
About Programming / Algorithms / haXe

Example of Coding on haXe (Dynamic and Recursive Fibonacci) – Part 3

In this example, you will see: private static function, recursive fibonacci and dynamic fibonacci algorithm.

NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.

example_3.hx:

/**
 * @author: Alejandro G. Carlstein R. M.
 */

class Example_3 {

	private static var fib_array : Array<Int> = [1, 1];

	static function main(){
		trace('main()');
		trace('Recursive Fibonacci (value: 5): ' + recursive_fib(5));
		trace('Dynamic Fibonacci (value: 5): ' + dynamic_fib(5));
		print_array();
	}

	// Recursive Fibonacci
	private static function recursive_fib(value : Int) : Int {
		if (value < 2)
			return 1;
		return recursive_fib(value - 1) + recursive_fib(value - 2);
	}

	// Dynamic Fibonacci
	private static function dynamic_fib(value : Int) : Int {
		if (value < 2)
			return 1;
		if (fib_array[value] == 0)
			fib_array[value] = dynamic_fib(value - 1) + dynamic_fib(value - 2);
		return fib_array[value];
	}

	private static function print_array() : Void{
		var iter = fib_array.iterator();
		while (iter.hasNext()){
			trace('Array Value: ' + iter.next());
		}
	}

}

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment
About Programming / Algorithms / ANSI/POSIX C

Example of Vertex Cover Algorithm using Heap

NOTIFICATION: These examples are provided for educational purposes. The use of this code and/or information is under your own responsibility and risk. The information and/or code is given ‘as is’. I do not take responsibilities of how they are used.

Example of Vertex Cover algorithm using heap.

vertex_cover.c:

/*
 * Program: 10
 * Author: Alejandro G. Carlstein
 * Description: Applying Vertex Cover Algorithm
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <errno.h>
#include <string.h>

#define MAX_EDGES 100001
#define MAX_VERTICES  50001
#define LEFT(i) ((i << 1) + 1)
#define RIGHT(i) ((i << 1) + 2)
#define DIV_BY_2(i) (i >> 1)
#define FALSE 0
#define TRUE 1

#define DBG_LV0 0
#define DBG_LV1 0
#define DBG_LV2 0
#define DBG_LV3 0

struct Edge{
	int id;
  int uVertex;
  int vVertex;
  short enabled;
} edges[MAX_EDGES];

struct Vertex{
	int id;
	int numEdges;
}vertices[MAX_VERTICES];

struct VertexCover{
	struct Vertex *vertexPointer;
	struct VertexCover *next;
};

struct AdjList{
	struct Edge *edgePointer;
	struct AdjList *next;
} *adjList[MAX_EDGES], *headAdj, *newAdj;

void readLimits(void);
void setVerticesDefault(void);
void readEdges(void);
void printEdges(void);
void printVertices(void);
struct VertexCover *vertexCover(void);
void makeMaxPriorityQueue(int heapArray[], int *length);
void printArray(int array[], int length);
void buildMaxHeap(int heapArray[], int length);
void maxHeapify(int heapArray[], int index, int heapSize);
int getMaxHeap(int heapArray[], int heapSize);
int heapExtractMax(int heapArray[], int *heapSize);
void exchange(int *a, int *b);
void buildAdjacentEdgesList(void);
void insertAdjEdgesOf(int edgeIndex);
void insertAdjEdge(int edgeIndex, int adjEdgeIndex);
void printAdjList(int edgeIndex);
void addVerticesOfEdgeToVertexCover(struct VertexCover *vertexCover, int vertexIndex);
void printvertexCover(struct VertexCover *vertexCover);
void debug(int debugLevel, char *fmt, ...);
void errorDoExit(char *fmt, ...);

int numVertices, numEdges;
int main(int argc, char *argv[]){
	readLimits();
	setVerticesDefault();
	readEdges();
	printvertexCover(vertexCover());
	return 0;
}

void readLimits(void){
	debug(DBG_LV0, 'readLimits()');	

	scanf('%d %d', &numVertices, &numEdges);
	debug(DBG_LV1, '# of vertices: %d, # of edges: %d', numVertices, numEdges);
}

void setVerticesDefault(void){
	debug(DBG_LV0, 'setVerticesDefault()');	

	int i;
	for (i = 0; i < numVertices; ++i){
		vertices[i].id = i;
		vertices[i].numEdges = 0;
	}
}

void readEdges(void){
	debug(DBG_LV0, 'readEdges()');	

	int i, uVertex, vVertex;
	for(i = 0; i < numEdges; ++i){
		int length;
		scanf('%d %d %d', &uVertex, &vVertex, &length);
		if (uVertex >= numVertices || vVertex >= numVertices)
			errorDoExit('Edge [%d](%d <> %d) have vertices id > %d', i, uVertex, vVertex, numVertices);
		edges[i].id = i;
		edges[i].uVertex = uVertex;
		edges[i].vVertex = vVertex;
		edges[i].enabled = TRUE;
		++vertices[uVertex].numEdges;
		++vertices[vVertex].numEdges;
	}	

	if (DBG_LV1) printEdges();
	if (DBG_LV1) printVertices();
}

void printEdges(){
	debug(DBG_LV0, 'printEdges()');

	int i;
	for(i = 0; i < numEdges; ++i)
		if (edges[i].enabled){
			printf('(%d<[%d]>%d)\n', edges[i].uVertex, i,edges[i].vVertex);
		}else{
			printf('(%d|[%d]|%d)\n', edges[i].uVertex, i,edges[i].vVertex);
		}
}

void printVertices(void){
	debug(DBG_LV0, 'printVertices()');

	printf('[  ]');
	int i;
	for (i = 0; i < numVertices; ++i)
		printf('[%d]', i);

	printf('\n[NE]');
	for (i = 0; i < numVertices; ++i)
		printf(' %d ' , vertices[i].numEdges);
	printf('\n');
}

struct VertexCover *vertexCover(void){
	debug(DBG_LV0, 'vertexCover()');

	// Build list of vertices that have the most number of edges
	int heapLength = numEdges + 1;
	int heapArray[heapLength];
	makeMaxPriorityQueue(heapArray, &heapLength);
	if (DBG_LV1) printArray(heapArray, heapLength);

	// Build Adjacent Vertices List
	buildAdjacentEdgesList();

	// Vertex cover to being constructed
	struct VertexCover *vertexCover = NULL;

	int edgeIndex;
	while(heapLength > 0){
		// Pick the edge in which vertices have the highest number of edges
		edgeIndex = heapExtractMax(heapArray, &heapLength);
		//Keep looping until you find an edge that is enabled or your count all the edges
		if (edges[edgeIndex].enabled){
			debug(DBG_LV1, 'EDGE FOUND: (%d<[%d]>%d)', edges[edgeIndex].uVertex, edgeIndex, edges[edgeIndex].vVertex);
		}else{
			debug(DBG_LV1, 'EDGE FOUND: (%d<|%d|>%d)', edges[edgeIndex].uVertex, edgeIndex, edges[edgeIndex].vVertex);
		}

		if (edges[edgeIndex].enabled){

			int uVertex = edges[edgeIndex].uVertex;
			int vVertex = edges[edgeIndex].vVertex;
			int uVertexNumEdges = vertices[uVertex].numEdges;
			int vVertexNumEdges = vertices[vVertex].numEdges;
			debug(DBG_LV1,'uVertex: %d, NumEdges: %d', uVertex, uVertexNumEdges);
			debug(DBG_LV1,'vVertex: %d, NumEdges: %d', vVertex, vVertexNumEdges);

			// Add this vertices of this edge to the list of edges
			struct VertexCover *newVertexCover = (struct VertexCover *) malloc(sizeof(struct VertexCover));
			newVertexCover->vertexPointer = &vertices[uVertex];
			if (vertexCover == NULL){
				debug(DBG_LV1, 'vertexCover is empty');
				newVertexCover->next = vertexCover;
				vertexCover = newVertexCover;
			}else{
				debug(DBG_LV1, 'vertexCover is NOT empty');
				struct VertexCover *currentVertexCover = vertexCover;
				while (currentVertexCover->next != NULL){
					currentVertexCover = currentVertexCover->next;
				}
				newVertexCover->next = currentVertexCover->next;
				currentVertexCover->next = newVertexCover;
			}
			debug(DBG_LV1, 'adding %d to vertexCover', newVertexCover->vertexPointer->id);			

			// Add this vertices of this edge to the list of edges
			newVertexCover = (struct VertexCover *) malloc(sizeof(struct VertexCover));
			newVertexCover->vertexPointer = &vertices[vVertex];
			if (vertexCover == NULL){
				debug(DBG_LV1, 'vertexCover is empty');
				newVertexCover->next = vertexCover;
				vertexCover = newVertexCover;
			}else{
				debug(DBG_LV1, 'vertexCover is NOT empty');
				struct VertexCover *currentVertexCover = vertexCover;
				while (currentVertexCover->next != NULL){
					currentVertexCover = currentVertexCover->next;
				}
				newVertexCover->next = currentVertexCover->next;
				currentVertexCover->next = newVertexCover;
			}
			debug(DBG_LV1, 'adding %d to vertexCover', newVertexCover->vertexPointer->id);			

			// Search thought all the adjacent edges to this edge and disable them
			struct AdjList *tempAdj;
			tempAdj = adjList[edgeIndex];
			while(tempAdj != NULL){
					debug(DBG_LV1, 'Disable Edge (%d<|%d|>%d)',
								tempAdj->edgePointer->uVertex, tempAdj->edgePointer->id, tempAdj->edgePointer->vVertex);
					tempAdj->edgePointer->enabled = FALSE;
					vertices[tempAdj->edgePointer->uVertex].numEdges--;
					vertices[tempAdj->edgePointer->vVertex].numEdges--;
				tempAdj = tempAdj->next;
			}
			edges[edgeIndex].enabled = FALSE;
			vertices[edges[edgeIndex].uVertex].numEdges--;
			vertices[edges[edgeIndex].vVertex].numEdges--;

		}
	}
	if(DBG_LV1) printEdges();

	return vertexCover;
}

void makeMaxPriorityQueue(int heapArray[], int *length){
	debug(DBG_LV0, 'makePriorityQueue(length: %d)', *length);

	int i;
	for (i = 0; i < numEdges; ++i)
		heapArray[i] = i;

	*length = numEdges;
	if (DBG_LV1) printArray(heapArray, *length);
	buildMaxHeap(heapArray, *length);
	if (DBG_LV1) printArray(heapArray, *length);
	if (DBG_LV1) printEdges();
}

void printArray(int array[], int length){
	debug(DBG_LV0, 'printArray(length: %d)', length);

	int i;
	for (i = 0; i < length; ++i)
		printf('[%d]', i);

	printf('\n');
	for (i = 0; i < length; ++i)
		printf(' %d ', array[i]);
	printf('\n');
}

void buildMaxHeap(int heapArray[], int length){
	debug(DBG_LV0, 'buildMaxHeap(length: %d)', length);

	int heapSize = length;

	int index;
	for (index = DIV_BY_2(length); index > -1; --index)
		maxHeapify(heapArray, index, heapSize);
}

void maxHeapify(int heapArray[], int index, int heapSize){
	debug(DBG_LV2, 'maxHeapify(index: %d, heapSize: %d)', index, heapSize);

	int largestIndex = index;
	int leftIndex = LEFT(index);
	int rightIndex = RIGHT(index);
	debug(DBG_LV2, '-LargestIndex: %d, leftIndex: %d, rightIndex: %d', largestIndex, leftIndex, rightIndex);

	if (leftIndex <= heapSize && rightIndex <= heapSize){

		unsigned int indexValue = vertices[edges[heapArray[index]].uVertex].numEdges +
															vertices[edges[heapArray[index]].vVertex].numEdges;

		unsigned long int leftValue = vertices[edges[heapArray[leftIndex]].uVertex].numEdges +
														 vertices[edges[heapArray[leftIndex]].vVertex].numEdges;

		if ((leftIndex < heapSize) && (leftValue > indexValue))
			largestIndex = leftIndex;
		debug(DBG_LV2, '(left) largestIndex: %d', largestIndex);

		debug(DBG_LV2, 'rightIndex: %d', rightIndex);
		debug(DBG_LV2, 'edges[%d].uVertex: %d, edges[%d].vVertex: %d',
										edges[heapArray[rightIndex]].uVertex,
										edges[heapArray[rightIndex]].vVertex);
		debug(DBG_LV2, 'uVertexNum: %d, vVertexNum: %d',
									vertices[edges[heapArray[rightIndex]].uVertex].numEdges,
								 vertices[edges[heapArray[rightIndex]].vVertex].numEdges);
		unsigned int rightValue = vertices[edges[heapArray[rightIndex]].uVertex].numEdges +
															vertices[edges[heapArray[rightIndex]].vVertex].numEdges;	

		if ((rightIndex < heapSize) && (rightValue > indexValue))
			largestIndex = rightIndex;
		debug(DBG_LV2, '(right) largestIndex: %d', largestIndex);

		if (largestIndex != index){
			debug(DBG_LV2, 'largestIndex != index');
			exchange(&heapArray[index], &heapArray[largestIndex]);
			maxHeapify(heapArray, largestIndex, heapSize);
		}
	}
}

int getMaxHeap(int heapArray[], int heapSize){
	debug(DBG_LV0, 'getMaxHeap(heapSize: %d)', heapSize);

	if (heapSize < 1)
		errorDoExit('Heap Underflow');
	int max = heapArray[0];
	return max;
}

int heapExtractMax(int heapArray[], int *heapSize){
	debug(DBG_LV0, 'heapExtractMax(heapSize: %d)', *heapSize);

	if (*heapSize < 1)
		errorDoExit('Heap Underflow');

	buildMaxHeap(heapArray, *heapSize);

	int max = heapArray[0];
	--*heapSize;
	heapArray[0] = heapArray[*heapSize];
	maxHeapify(heapArray, 1, *heapSize);

	return max;
}

void exchange(int *a, int *b){
	debug(DBG_LV3, 'exchange(a: %d, b: %d)', *a, *b);

		int temp;
		temp = *a;
		*a = *b;
		*b = temp;
}

void buildAdjacentEdgesList(void){
	debug(DBG_LV0, 'buildAdjacentEdgesList()');

	int edgeIndex;
	for (edgeIndex = 0; edgeIndex < numEdges; ++edgeIndex){
		insertAdjEdgesOf(edgeIndex);
	}

	if (DBG_LV1)
		for (edgeIndex = 0; edgeIndex < numEdges; ++edgeIndex)
			printAdjList(edgeIndex);
}

void insertAdjEdgesOf(int edgeIndex){
	debug(DBG_LV0, 'insertAdjEdgesOf(edgeIndex: %d)', edgeIndex);	

	debug(DBG_LV1, ' Searching for adjacent Edges');
	int adjEdgeIndex;
	for (adjEdgeIndex = 0; adjEdgeIndex < numEdges; ++adjEdgeIndex){
		if (edgeIndex != adjEdgeIndex){
			int uVertex = edges[edgeIndex].uVertex;
			int vVertex = edges[edgeIndex].vVertex;
			int adjUVertex = edges[adjEdgeIndex].uVertex;
			int adjVVertex = edges[adjEdgeIndex].vVertex;
			debug(DBG_LV1, '  (%d <[%d]> %d) <=?=> A(%d <[%d]> %d)', uVertex, edgeIndex, vVertex, adjUVertex, adjEdgeIndex, adjVVertex);
			if (uVertex == adjUVertex || vVertex == adjVVertex ||
					uVertex == adjVVertex || vVertex == adjUVertex){
				debug(DBG_LV1, '   YES');
				insertAdjEdge(edgeIndex, adjEdgeIndex);
			}
		}
	}
	if(DBG_LV1) printAdjList(edgeIndex);
}

void insertAdjEdge(int edgeIndex, int adjEdgeIndex){

	struct AdjList *headAdj;
	headAdj = adjList[edgeIndex];	

	struct AdjList *newAdj = (struct AdjList *) malloc(sizeof(struct AdjList));
	newAdj->edgePointer = &edges[adjEdgeIndex];
	newAdj->next = NULL;

	if (headAdj == NULL){
		newAdj->next = adjList[edgeIndex];
		adjList[edgeIndex] = newAdj;
	}else{
		struct AdjList *currentAdj = adjList[edgeIndex];
		while (currentAdj->next != NULL)
			currentAdj = currentAdj->next;
		newAdj->next = currentAdj->next;
		currentAdj->next = newAdj;
	}
}

void printAdjList(int edgeIndex){
	debug(DBG_LV0, '**printAdjList(edgeIndex: %d)', edgeIndex);	

	struct AdjList *tempAdj;
	tempAdj = adjList[edgeIndex];	

	if (tempAdj == NULL){
		debug(DBG_LV1, ' tempAdj is empty');
	}else{		

		printf('[%d]', edgeIndex);
		int i = 0;
		while(tempAdj != NULL){
			printf('|%d|', i++);
			tempAdj = tempAdj->next;
		}

		printf('\n i:');
		tempAdj = adjList[edgeIndex];
		while(tempAdj != NULL){
			printf('[%d]', tempAdj->edgePointer->id);
			tempAdj = tempAdj->next;
		}

		printf('\n u:');
		tempAdj = adjList[edgeIndex];
		while(tempAdj != NULL){
				printf(' %d ' , tempAdj->edgePointer->uVertex);
				tempAdj = tempAdj->next;
		}

		printf('\n v:');
		tempAdj = adjList[edgeIndex];
		while(tempAdj != NULL){
				printf(' %d ' , tempAdj->edgePointer->vVertex);
				tempAdj = tempAdj->next;
		}

		printf('\n');
	}
}

void addVerticesOfEdgeToVertexCover(struct VertexCover *vertexCover, int vertexIndex){
	debug(DBG_LV0, 'addVerticesOfEdgeToVertexCover(vertexIndex: %d)', vertexIndex);	

	struct VertexCover *newVertexCover = (struct VertexCover *) malloc(sizeof(struct VertexCover));
	newVertexCover->vertexPointer = &vertices[vertexIndex];
	if (vertexCover == NULL){
		debug(DBG_LV1, 'vertexCover is empty');
		newVertexCover->next = vertexCover;
		vertexCover = newVertexCover;
		debug(DBG_LV1, 'adding %d to vertexCover', newVertexCover->vertexPointer->id);
	}else{
		struct VertexCover *currentVertexCover = vertexCover;
		debug(DBG_LV1, 'adding %d to vertexCover', currentVertexCover->vertexPointer->id);
		while (currentVertexCover->next != NULL){
			debug(DBG_LV1, 'vertexId: %d', currentVertexCover->vertexPointer->id);
			currentVertexCover = currentVertexCover->next;
		}
		newVertexCover->next = currentVertexCover->next;
		currentVertexCover->next = newVertexCover;
	}	

}

void printvertexCover(struct VertexCover *vertexCover){
	debug(DBG_LV0, 'printvertexCover');	

	struct VertexCover *tempAdj;
	tempAdj = vertexCover;	

	if (tempAdj == NULL){
		debug(DBG_LV1, ' tempAdj is empty');
	}else{		

		while(tempAdj != NULL){
			printf('%d ', tempAdj->vertexPointer->id);
			tempAdj = tempAdj->next;
		}

		printf('\n');
	}
}

void debug(int debugLevel, char *fmt, ...){
	if (debugLevel == 1){
		va_list argp;
		fprintf(stdout, '[DBG] ');
		va_start(argp, fmt);
		vfprintf(stdout, fmt, argp);
		va_end(argp);
		fprintf(stdout, '\n');
	}
}

void errorDoExit(char *fmt, ...){
	va_list argp;
	fprintf(stderr, '[Error] ');
	va_start(argp, fmt);
	vfprintf(stderr, fmt, argp);
	va_end(argp);
	if (errno){
		fprintf(stderr, '=> %s\n', strerror(errno));
	}else{
		fprintf(stderr, '\n');
	}
	exit(1);
}

input.txt:

4 7

0 1 5

0 2 4

1 3 3

2 3 2

3 0 1

2 1 10

0 3 20

If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.

Share
Leave a comment