DZone Snippets: algorithm code

Bit field class

phaana (Irfan Hamid) — Thu, 15 May 2008 11:48:59 GMT

// A bit field is an important data structure in computer science, major uses include memory allocators and Bloom filters.
// The code is in the form of a header file and an implementation file.





// This class is a code snippet, it can be freely used and distributed.

// Author: irfan[dot]hamid[at]gmail[dot]com

//

// Bit fields are a widely used mechanism in computing applications.

// Typical applications include memory allocators and Bloom filters. This class

// provides a generic bit field implementation for an arbitrary number of bits.

//

// Implementation notes:

// The use of C++ allows the clean separation of the data structure from the

// interface. The bit field is implemented as a vector of unsigned int that is

// allocated at object creation.

//

// field: The vector that represents the bit field itself

// bit_count: The total number of bits in the bit field



#ifndef __BITFIELD_H__

#define __BITFIELD_H__

#include 

#define SZ_UINT sizeof(unsigned int)



class Bitfield

{

protected:

	unsigned int *field;

	unsigned int bit_count;



public:

	Bitfield (int bc);

	~Bitfield ();



	int set (int bit);

	int get (int bit);

	int reset (int bit);

};



#endif







#include 

#include "bitfield.h"



// The constructor takes an int param which gives the number of bits in this

// bit field.

Bitfield::Bitfield (int bc)

{

	bit_count = bc;



	// E.g, ceil(257/32*8) = 65, 64 ints fully used, last one partially used

	field = (unsigned int*) malloc(((int) ceil(bc/SZ_UINT*8)));

}



Bitfield::~Bitfield ()

{

	if (field)

		free(field);

}



// This function sets the corresponding bit in the field equal to 1.

//

// Returns: 0 on success, -1 on error.

int Bitfield::set (int bit)

{

	// Sanity check

	if (bit >= bit_count || !field)

		return -1;



	// The correct index into the vector will be given by bit/SZ_UNIT. The

	// index into the correct vector element is given by bit%SZ_UNIT, to

	// achieve this, simply left shift 0x01 the appropriate number of times.

	field[bit/SZ_UINT] |= (0x00000001 << (bit%(SZ_UINT*8)-1));

	return 0;

}



// This function sets the corresponding bit in the field equal to 0.

//

// Returns: 0 on success, -1 on error.

int Bitfield::reset (int bit)

{

	if (bit >= bit_count || !field)

		return -1;

	field[bit/SZ_UINT] &= ~(0x00000001 << (bit%(SZ_UINT*8)-1));

	return 0;

}



// This function returns the value of the corresponding bit.

//

// Returns: The value of the bit, if the field is initialized and bit index is

// within bounds, -1 otherwise.

int Bitfield::get (int bit)

{

	if (bit >= bit_count || !field)

		return -1;

	return (field[bit/SZ_UINT] & (0x00000001 << (bit%(SZ_UINT*8)-1)) ? 1 : 0);

}

Fast anagram determination

phaana (Irfan Hamid) — Wed, 14 May 2008 23:40:31 GMT

// This function will determine whether the two C strings provided are anagrams or not. Only alphabetical strings are considered.



/******************************************************************************

 * This function is a code snippet. It can be freely used and distributed.

 * Author: irfan[dot]hamid[at]gmail[at]com

 *

 * This function takes two ASCII strings in C syntax (null-terminated

 * character arrays) and determines whether they are anagrams or not.

 *

 * Implementation notes:

 * The function contains a histogram that stores the frequency of each 

 * character it encounters in the first string. For each character of the 

 * second string, it decrements the corresponding entry in the histogram. If 

 * before every decrement, the value of the histogram bucket reaches zero, 

 * then the two strings are not anagrams, as there is some character that has

 * more occurrences in the second string than in the first string.

 *

 * If either of the two strings contains a non-alphabetic character, the

 * anagram property is considered to be violated.

 *

 * Remarks:

 * It is an efficient implementation because:

 *   o It is in-place, the original strings are not copied, no alloc or copy

 *   o Does not clobber the original strings

 *   o It is a linear time implementation

 *

 * Returns:

 * True if the strings are anagrams, false otherwise.

******************************************************************************/



bool is_anagram (char w1[], char w2[])

{

	unsigned int i, sz;



	/* The histogram */

	int freqtbl[26];



	/* Sanity check */

	if ((sz = strlen(w1)) != strlen(w2))

		return false;



	/* Initialize the histogram */

	bzero(freqtbl, 26*sizeof(int));



	/* Read the first string, incrementing the corresponding histogram entry */

	for (i = 0; i < sz; i++) {

		if (w1[i] >= 'A' && w1[i] <= 'Z')

			freqtbl[w1[i]-'A']++;

		else if (w1[i] >= 'a' && w1[i] <= 'z')

			freqtbl[w1[i]-'a']++;

		else

			return false;

	}



	/* Read the second string, decrementing the corresponding histogram entry */

	for (i = 0; i < sz; i++) {

		if (w2[i] >= 'A' && w2[i] <= 'Z') {

			if (freqtbl[w2[i]-'A'] == 0)

				return false;

			freqtbl[w2[i]-'A']--;

		} else if (w2[i] >= 'a' && w2[i] <= 'z') {

			if (freqtbl[w2[i]-'a'] == 0)

				return false;

			freqtbl[w2[i]-'a']--;

		} else {

			return false;

		}

	}



	return true;

}

Speeding up Dijkstra's Algorithm

scvalex (Alexandru Scvortov) — Thu, 17 Jan 2008 15:57:42 GMT

Demonstrates a way of speeding up the O(n²) version of Dijkstra's Algorithm by about 4x.

Here, dist[][] is the adjacency matrix representing the graph and n is the number of nodes. d2[] is where the lengths of the shortest paths are saved.

For a full explanation, see this.



void dijkstra2(int s) {

	int queue[GRAPHSIZE];

	char inQueue[GRAPHSIZE];

	int begq = 0,

	    endq = 0;

	int i, mini;

	int visited[GRAPHSIZE];



	for (i = 1; i <= n; ++i) {

		d2[i] = INFINITY;

		visited[i] = 0; /* the i-th element has not yet been visited */

		inQueue[i] = 0;

	}



	d2[s] = 0;

	queue[endq] = s;

	endq = (endq + 1) % GRAPHSIZE;





	while (begq != endq) {

		mini = queue[begq];

		begq = (begq + 1) % GRAPHSIZE;

		inQueue[mini] = 0;



		visited[mini] = 1;



		for (i = 1; i <= n; ++i)

			if (dist[mini][i])

				if (d2[mini] + dist[mini][i] < d2[i]) { 

					d2[i] = d2[mini] + dist[mini][i];

					if (!inQueue[i]) {

						queue[endq] = i;

						endq = (endq + 1) % GRAPHSIZE;

						inQueue[i] = 1;

					}

				}

	}

}

Gaussian Elimination in C

scvalex (Alexandru Scvortov) — Tue, 11 Dec 2007 13:46:27 GMT

This is a simple implementation of the Gaussian Elimination algorithm for solving n linear equations with n unknowns.

Further explanation is given here.



#include 



int n;

float a[10][11];



void forwardSubstitution() {

	int i, j, k, max;

	float t;

	for (i = 0; i < n; ++i) {

		max = i;

		for (j = i + 1; j < n; ++j)

			if (a[j][i] > a[max][i])

				max = j;

		

		for (j = 0; j < n + 1; ++j) {

			t = a[max][j];

			a[max][j] = a[i][j];

			a[i][j] = t;

		}

		

		for (j = n; j >= i; --j)

			for (k = i + 1; k < n; ++k)

				a[k][j] -= a[k][i]/a[i][i] * a[i][j];



/*		for (k = 0; k < n; ++k) {

			for (j = 0; j < n + 1; ++j)

				printf("%.2f\t", a[k][j]);

			printf("\n");

		}*/

	}

}



void reverseElimination() {

	int i, j;

	for (i = n - 1; i >= 0; --i) {

		a[i][n] = a[i][n] / a[i][i];

		a[i][i] = 1;

		for (j = i - 1; j >= 0; --j) {

			a[j][n] -= a[j][i] * a[i][n];

			a[j][i] = 0;

		}

	}

}



void gauss() {

	int i, j;



	forwardSubstitution();

	reverseElimination();

	

	for (i = 0; i < n; ++i) {

		for (j = 0; j < n + 1; ++j)

			printf("%.2f\t", a[i][j]);

		printf("\n");

	}

}



int main(int argc, char *argv[]) {

	int i, j;



	FILE *fin = fopen("gauss.in", "r");

	fscanf(fin, "%d", &n);

	for (i = 0; i < n; ++i)

		for (j = 0; j < n + 1; ++j)

			fscanf(fin, "%f", &a[i][j]);

	fclose(fin);

	

	gauss();

	

	return 0;

}

Dijkstra's Algorithm

scvalex (Alexandru Scvortov) — Sat, 01 Dec 2007 19:41:53 GMT

This is a simple O(n^2) implementation of Dijkstra's algorithm for finding the shortest paths from a single source to all nodes in a graph.

Further explanation is given here.



#include 



#define GRAPHSIZE 2048

#define INFINITY GRAPHSIZE*GRAPHSIZE

#define MAX(a, b) ((a > b) ? (a) : (b))



int e; /* The number of nonzero edges in the graph */

int n; /* The number of nodes in the graph */

long dist[GRAPHSIZE][GRAPHSIZE]; /* dist[i][j] is the distance between node i and j; or 0 if there is no direct connection */

long d[GRAPHSIZE]; /* d[i] is the length of the shortest path between the source (s) and node i */



void printD() {

	int i;

	for (i = 1; i <= n; ++i)

		printf("%10d", i);

	printf("\n");

	for (i = 1; i <= n; ++i) {

		printf("%10ld", d[i]);

	}

	printf("\n");

}



void dijkstra(int s) {

	int i, k, mini;

	int visited[GRAPHSIZE];



	for (i = 1; i <= n; ++i) {

		d[i] = INFINITY;

		visited[i] = 0; /* the i-th element has not yet been visited */

	}



	d[s] = 0;



	for (k = 1; k <= n; ++k) {

		mini = -1;

		for (i = 1; i <= n; ++i)

			if (!visited[i] && ((mini == -1) || (d[i] < d[mini])))

				mini = i;



		visited[mini] = 1;



		for (i = 1; i <= n; ++i)

			if (dist[mini][i])

				if (d[mini] + dist[mini][i] < d[i]) 

					d[i] = d[mini] + dist[mini][i];

	}

}



int main(int argc, char *argv[]) {

	int i, j;

	int u, v, w;



	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &e);

	for (i = 0; i < e; ++i)

		for (j = 0; j < e; ++j)

			dist[i][j] = 0;

	n = -1;

	for (i = 0; i < e; ++i) {

		fscanf(fin, "%d%d%d", &u, &v, &w);

		dist[u][v] = w;

		n = MAX(u, MAX(v, n));

	}

	fclose(fin);



	dijkstra(1);



	printD();



	return 0;

}

Bellman-Ford Algorithm

scvalex (Alexandru Scvortov) — Thu, 29 Nov 2007 14:55:34 GMT

This is a simple implementation of the Bellman-Ford algorithm for finding the shortest path from a single source in a graph.

A detailed explanation is given here.



#include 



typedef struct {

	int u, v, w;

} Edge;



int n; /* the number of nodes */

int e; /* the number of edges */

Edge edges[1024]; /* large enough for n <= 2^5=32 */

int d[32]; /* d[i] is the minimum distance from node s to node i */



#define INFINITY 10000



void printDist() {

	int i;



	printf("Distances:\n");



	for (i = 0; i < n; ++i)

		printf("to %d\t", i + 1);

	printf("\n");



	for (i = 0; i < n; ++i)

		printf("%d\t", d[i]);



	printf("\n\n");

}



void bellman_ford(int s) {

	int i, j;



	for (i = 0; i < n; ++i)

		d[i] = INFINITY;



	d[s] = 0;



	for (i = 0; i < n - 1; ++i)

		for (j = 0; j < e; ++j)

			if (d[edges[j].u] + edges[j].w < d[edges[j].v])

				d[edges[j].v] = d[edges[j].u] + edges[j].w;

}



int main(int argc, char *argv[]) {

	int i, j;

	int w;



	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &n);

	e = 0;



	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j) {

			fscanf(fin, "%d", &w);

			if (w != 0) {

				edges[e].u = i;

				edges[e].v = j;

				edges[e].w = w;

				++e;

			}

		}

	fclose(fin);



	/* printDist(); */



	bellman_ford(0);



	printDist();



	return 0;

}

The 0-1 Knapsack Problem in C

scvalex (Alexandru Scvortov) — Tue, 20 Nov 2007 17:17:50 GMT

This is a dynamic-programming algorithm implementation for solving the the 0-1 Knapsack Problem in C.

Further explanation is given here.



#include 



#define MAXWEIGHT 100



int n = 3; /* The number of objects */

int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what

				YOU PAY to take the object */

int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e.

				what YOU GET for taking the object */

int W = 10; /* The maximum weight you can take */ 



void fill_sack() {

	int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained

				using at most i weight */

	int last_added[MAXWEIGHT]; /* I use this to calculate which object were

					added */

	int i, j;

	int aux;



	for (i = 0; i <= W; ++i) {

		a[i] = 0;

		last_added[i] = -1;

	}



	a[0] = 0;

	for (i = 1; i <= W; ++i)

		for (j = 0; j < n; ++j)

			if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) {

				a[i] = a[i - c[j]] + v[j];

				last_added[i] = j;

			}



	for (i = 0; i <= W; ++i)

		if (last_added[i] != -1)

			printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[i]]);

		else

			printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);



	printf("---\n");



	aux = W;

	while ((aux > 0) && (last_added[aux] != -1)) {

		printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);

		aux -= c[last_added[aux]];

	}



	printf("Total value added: %d$\n", a[W]);

}



int main(int argc, char *argv[]) {

	fill_sack();



	return 0;

}

The Fractional Knapsack Problem in C

scvalex (Alexandru Scvortov) — Tue, 20 Nov 2007 13:39:13 GMT

This is the classic Greedy algorithm implementation for solving the Fractional Knapsack Problem in C.

Further explanations here



#include 



int n = 5; /* The number of objects */

int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what

				YOU PAY to take the object */

int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e.

				what YOU GET for taking the object */

int W = 15; /* The maximum weight you can take */



void simple_fill() {

	int cur_w;

	float tot_v;

	int i, maxi;

	int used[10];



	for (i = 0; i < n; ++i)

		used[i] = 0; /* I have not used the ith object yet */



	cur_w = W;

	while (cur_w > 0) { /* while there's still room*/

		/* Find the best object */

		maxi = -1;

		for (i = 0; i < n; ++i)

			if ((used[i] == 0) &&

				((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))

				maxi = i;



		used[maxi] = 1; /* mark the maxi-th object as used */

		cur_w -= c[maxi]; /* with the object in the bag, I can carry less */

		tot_v += v[maxi];

		if (cur_w >= 0)

			printf("Added object %d (%d$, %dKg) completly in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);

		else {

			printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);

			tot_v -= v[maxi];

			tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];

		}

	}



	printf("Filled the bag with objects worth %.2f$.\n", tot_v);

}



int main(int argc, char *argv[]) {

	simple_fill();



	return 0;

}

All Sources Shortest Path: The Floyd-Warshall Algorithm

scvalex (Alexandru Scvortov) — Thu, 15 Nov 2007 16:19:25 GMT

This is a straightforward implementation of the Floyd-Warshall algorithm for finding the shortest path between all nodes of a graph.

A more detailed explanation is given here.



#include 



int n; /* Then number of nodes */

int dist[16][16]; /* dist[i][j] is the length of the edge between i and j if

			it exists, or 0 if it does not */



void printDist() {

	int i, j;

	printf("    ");

	for (i = 0; i < n; ++i)

		printf("%4c", 'A' + i);

	printf("\n");

	for (i = 0; i < n; ++i) {

		printf("%4c", 'A' + i);

		for (j = 0; j < n; ++j)

			printf("%4d", dist[i][j]);

		printf("\n");

	}

	printf("\n");

}



/*

	floyd_warshall()



	after calling this function dist[i][j] will the the minimum distance

	between i and j if it exists (i.e. if there's a path between i and j)

	or 0, otherwise

*/

void floyd_warshall() {

	int i, j, k;

	for (k = 0; k < n; ++k) {

		printDist();

		for (i = 0; i < n; ++i)

			for (j = 0; j < n; ++j)

				/* If i and j are different nodes and if 

					the paths between i and k and between

					k and j exist, do */

				if ((dist[i][k] * dist[k][j] != 0) && (i != j))

					/* See if you can't get a shorter path

						between i and j by interspacing

						k somewhere along the current

						path */

					if ((dist[i][k] + dist[k][j] < dist[i][j]) ||

						(dist[i][j] == 0))

						dist[i][j] = dist[i][k] + dist[k][j];

	}

	printDist();

}



int main(int argc, char *argv[]) {

	FILE *fin = fopen("dist.txt", "r");

	fscanf(fin, "%d", &n);

	int i, j;

	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j)

			fscanf(fin, "%d", &dist[i][j]);

	fclose(fin);



	floyd_warshall();



	return 0;

}

Prim's Algorithm for Finding Minimum Spanning Trees in C

scvalex (Alexandru Scvortov) — Fri, 09 Nov 2007 12:31:11 GMT

The is a straight-forward implementation of Prim's Algorithm for finding the minimum spanning tree of a graph.

A detailed explanation is given here.



#include 



/*

	The input file (weight.txt) look something like this

		4

		0 0 0 21

		0 0 8 17

		0 8 0 16

		21 17 16 0



	The first line contains n, the number of nodes.

	Next is an nxn matrix containg the distances between the nodes

	NOTE: The distance between a node and itself should be 0

*/



int n; /* The number of nodes in the graph */



int weight[100][100]; /* weight[i][j] is the distance between node i and node j;

			if there is no path between i and j, weight[i][j] should

			be 0 */



char inTree[100]; /* inTree[i] is 1 if the node i is already in the minimum

			spanning tree; 0 otherwise*/



int d[100]; /* d[i] is the distance between node i and the minimum spanning

		tree; this is initially infinity (100000); if i is already in

		the tree, then d[i] is undefined;

		this is just a temporary variable. It's not necessary but speeds

		up execution considerably (by a factor of n) */



int whoTo[100]; /* whoTo[i] holds the index of the node i would have to be

			linked to in order to get a distance of d[i] */



/* updateDistances(int target)

	should be called immediately after target is added to the tree;

	updates d so that the values are correct (goes through target's

	neighbours making sure that the distances between them and the tree

	are indeed minimum)

*/

void updateDistances(int target) {

	int i;

	for (i = 0; i < n; ++i)

		if ((weight[target][i] != 0) && (d[i] > weight[target][i])) {

			d[i] = weight[target][i];

			whoTo[i] = target;

		}

}



int main(int argc, char *argv[]) {

	FILE *f = fopen("dist.txt", "r");

	fscanf(f, "%d", &n);

	int i, j;

	for (i = 0; i < n; ++i)

		for (j = 0; j < n; ++j)

			fscanf(f, "%d", &weight[i][j]);

	fclose(f);



	/* Initialise d with infinity */

	for (i = 0; i < n; ++i)

		d[i] = 100000;



	/* Mark all nodes as NOT beeing in the minimum spanning tree */

	for (i = 0; i < n; ++i)

		inTree[i] = 0;



	/* Add the first node to the tree */

	printf("Adding node %c\n", 0 + 'A');

	inTree[0] = 1;

	updateDistances(0);



	int total = 0;

	int treeSize;

	for (treeSize = 1; treeSize < n; ++treeSize) {

		/* Find the node with the smallest distance to the tree */

		int min = -1;

		for (i = 0; i < n; ++i)

			if (!inTree[i])

				if ((min == -1) || (d[min] > d[i]))

					min = i;



		/* And add it */

		printf("Adding edge %c-%c\n", whoTo[min] + 'A', min + 'A');

		inTree[min] = 1;

		total += d[min];



		updateDistances(min);

	}



	printf("Total distance: %d\n", total);



	return 0;

}