Example of using Fork and pipe in Linux

The following program will create a chain of parents/child in which the last child will receive a message form the top parent through a pipe.

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.

The first example is without using recursion while the second example is the same thing but using example. In this way, you can see how fork and pipe behaves.

for_pipe_without_using_recursion.c:

/**
 * @author: Alejandro G. Carlstein R. M.
 * @description: This program will take an integer argument.
 *               It will create a chain of parent-child equal to the value
 *               provided by the integer argument, Example:
 *				 Top parent - forks ==> 
 * 				 child1 - forks ==> 
 *				 child1's child - forks ... ==> Nth generation child, where
 *				 N is the integer argument.
 *			     Then the top parent will then pass a message to 
 *               the child at the lowest level (Nth generation child) 
 *               through a pipe. That child will print 
 *               the received message to output stdout.
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>

#define MAX_N 3
#define IDX_ARG_N 1
#define MAX_BUFF 30

int read_pipe(int *pfds, char msg[], int max_buff, int i_tab);

int write_pipe(int *pfds, const char *msg, int max_buff, int i_tab);

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

	pid_t rtn_pid, pid[3];

	int rtn_error = 0;

	int i, j, status;

	int pfds[2];

	int i_N = (argc > 2) ? atoi(argv[IDX_ARG_N]): 0;

	char buf[MAX_BUFF];

	printf('\n');

	/* create a pipe */
    if (pipe(pfds) == -1) {
            perror('pipe');
            exit(1);
    }else{

		/* fork first child */
    	if ( (pid[0] = fork()) < 0) {
			perror('fork pid[0]');
			exit(1);
    	}// end if

    	/* Parent of first fork */
    	if (pid[0] > 0){

    		printf('Parent of first fork sending message: Hello! \n');    	

    		rtn_error = write_pipe(pfds, 'Hello! \n', MAX_BUFF, 0);	 

    		//close(pfds[0]);
    		//close(pfds[1]);

    	}//end if

    	/* Child of first fork */
    	if (pid[0] == 0){

    		printf('>>Child of first fork \n');

			/* fork second child */
	    	if ( (pid[1] = fork()) < 0) {
				perror('fork pid[1]');
				exit(1);
	    	}// end if

	    	/* Parent of second fork */
	    	if (pid[1] > 0){

	    		//printf('Parent of second fork...\n');    	

			}//end if

	    	/* Child of second fork */
	    	if (pid[1] == 0){

		    	printf('>>>>Child of second fork \n');

				/* fork third child */
		    	if ( (pid[2] = fork()) < 0) {
					perror('fork pid[2]');
					exit(1);
		    	}// end if

		    	/* Parent of third fork */
		    	if (pid[2] > 0){

		    		//printf('Parent of third fork...\n');    	

				}//end if		    	

		    	/* Child of third fork */
		    	if (pid[2] == 0){

			    	printf('>>>>>Child of third fork \n');

					rtn_error = read_pipe(pfds, buf, MAX_BUFF, 5);

					if (rtn_error == 0){
						printf('>>>>>CHILD OF THIRD FORK READ MESSAGE: %s \n',  buf);
					}//end if

		    	}//end if

	    	}//end if

    	}//end if

		wait();

	}// end if

	return rtn_error;
}

int write_pipe(int *pfds, const char *msg, int max_buff, int i_tab){

		int rtn_error = 0;

		/* close the read end */
		close(pfds[0]);

		//printf ('%*sWRITE_PIPE: %s\n', i_tab, ' ', msg);

		/* write message to parent  through the write end */
        if(write(pfds[1], msg, max_buff) <= 0) {

			printf('%*s[X] ERROR: Cannot write\n', i_tab, ' ');

			rtn_error = 1;

		}//end if

	return rtn_error;
}

int read_pipe(int *pfds, char msg[], int max_buff, int i_tab){

		int rtn_error = 0;

		/* close the write end */
		close(pfds[1]);

		//printf ('%*sREAD_PIPE: ', i_tab, ' ');

		/* read message from child through the read end */
		// If not data in the pipe, the read will block
	    if( read(pfds[0], msg, max_buff) <= 0 ) {

			printf ( '%*s[X] ERROR: Cannot read\n', i_tab, ' ');

			rtn_error = 1;

		}else{

			//printf('%*s%s \n', i_tab, ' ', msg);		

		}//end if

	return rtn_error;
}

fork_pipe_using_recursion.c:

/**
 * @author: Alejandro G. Carlstein R. M.
 * @description: This program will take an integer argument.
 *               It will create a chain of parent-child equal to the value
 *               provided by the integer argument, Example:
 *				 Top parent - forks ==>
 * 				 child1 - forks ==>
 *				 child1's child - forks ... ==> Nth generation child, where
 *				 N is the integer argument.
 *			     Then the top parent will then pass a message to
 *               the child at the lowest level (Nth generation child)
 *               through a pipe. That child will print
 *               the received message to output stdout.
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>

#define MAX_N 3
#define IDX_ARG_N 1
#define MAX_BUFF 30
#define DBG_LV1 0
#define DBG_LV2 1
#define MSG 'Hello! \n'

int read_pipe(int *pfds, char msg[], int max_buff, int i_tab);

int write_pipe(int *pfds, const char *msg, int max_buff, int i_tab);

int recursive_f(int *pfds, int i_count, int i_max_count);

int exec_order;

int main(int argc, char *argv[])
{
	pid_t rtn_pid, pid[3];

	int rtn_error = 0;

	int i, status;

	int pfds[2];

	int i_N = (argc > 2) ? atoi(argv[IDX_ARG_N]): 0;

	exec_order = 0;

	printf('\n');

	/* create a pipe */
    if (pipe(pfds) == -1) {
            perror('pipe');
            exit(1);
    }else{

    	rtn_error = recursive_f(pfds, MAX_N, MAX_N);

	}// end if

	close(pfds[0]);
	close(pfds[1]);

	for (i = 0; i < MAX_N - 1; i++){
		wait();
	}

	return rtn_error;
}

int recursive_f(int *pfds, int i_count, int i_max_count){

	int rtn_error = 0;

	char buf[MAX_BUFF];

	pid_t pid;

	if (DBG_LV1){

   		printf('[e_o: %d][count: %d/%d] recursive_f (*pfds, %d, %d)\n',
   			  exec_order, i_count, i_max_count, i_count, i_max_count);

	}//end if

	/* fork */
    if ( ( pid = fork() ) < 0) {

		if (DBG_LV2)
			perror('error fork pid');

		rtn_error = 1;

    }else{

    	/* Parent of first fork */
    	if (pid > 0 && i_count == i_max_count){

	   		if (DBG_LV1)
	   			printf('[e_o: %d][count: %d/%d] ', exec_order, i_count, i_max_count);

    		printf('Parent of first fork sending message: %s', MSG);    	

    		rtn_error = write_pipe(pfds, MSG, MAX_BUFF, 0);	 

	   		if (DBG_LV1)
	   			printf('[e_o: %d][count: %d/%d] ', exec_order, i_count, i_max_count);

    		printf('PARENT OF FIRST FORK SENT MESSAGE: %s', MSG);

    	}else{
	    	exec_order++;   	

    	}//end if

		/* Child of last fork */
		if (pid == 0){

			if (i_count < 1){

		   		if (DBG_LV1)
		   			printf('[e_o: %d][count: %d/%d] ', exec_order, i_count, i_max_count);

				printf('Last Child of fork reading...\n');

				rtn_error = read_pipe(pfds, buf, MAX_BUFF, 5);

				if (rtn_error == 0){

			   		if (DBG_LV1)
			   			printf('[e_o: %d][count: %d/%d] ', exec_order, i_count, i_max_count);

					printf('LAST CHILD OF FORK READ MESSAGE: %s', buf);

				}//end if

			}else{

	  			i_count--;

	  			if (DBG_LV1)
		  			printf('[e_o: %d][count: %d/%d] Calling recursive_f (i_count[%d] and i_max_count[%d]) \n',
		  				   exec_order, i_count, i_max_count, i_count, i_max_count);

	  			rtn_error = recursive_f(pfds, i_count, i_max_count);

	  		}//end if

    	}//end if

    }// end if	

	return rtn_error;
}

int write_pipe(int *pfds, const char *msg, int max_buff, int i_tab){

		int rtn_error = 0;

		/* close the read end */
		close(pfds[0]);

		if (DBG_LV1) printf ('%*sWRITE_PIPE: %s\n', i_tab, ' ', msg);

		/* write message to parent  through the write end */
        if(write(pfds[1], msg, max_buff) <= 0) {

			if (DBG_LV2) printf('%*s[X] ERROR: Cannot write\n', i_tab, ' ');

			rtn_error = 1;

		}//end if

	return rtn_error;
}

int read_pipe(int *pfds, char msg[], int max_buff, int i_tab){

		int rtn_error = 0;

		/* close the write end */
		close(pfds[1]);

		if (DBG_LV1) printf ('%*sREAD_PIPE: ', i_tab, ' ');

		/* read message from child through the read end */
		// If not data in the pipe, the read will block
	    if( read(pfds[0], msg, max_buff) <= 0 ) {

			if (DBG_LV2) printf ( '%*s[X] ERROR: Cannot read\n', i_tab, ' ');

			rtn_error = 1;

		}else{

			if (DBG_LV1) printf('%*s%s \n', i_tab, ' ', msg);		

		}//end if

	return rtn_error;
}

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

/**
* @course: CS350 Lab
* @author: Alejandro G. Carlstein R. M.
* @description: This program will take an integer argument.
*               It will create a chain of parent-child equal to the value
*               provided by the integer argument, Example:
*                 Top parent – forks ==>
*                  child1 – forks ==>
*                 child1’s child – forks … ==> Nth generation child, where
*                 N is the integer argument.
*                 Then the top parent will then pass a message to
*               the child at the lowest level (Nth generation child)
*               through a pipe. That child will print
*               the received message to output stdout.
*/

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>

#define MAX_N 3
#define IDX_ARG_N 1
#define MAX_BUFF 30
#define DBG_LV1 0
#define DBG_LV2 1
#define MSG “Hello! \n”

int read_pipe(int *pfds, char msg[], int max_buff, int i_tab);

int write_pipe(int *pfds, const char *msg, int max_buff, int i_tab);

int recursive_f(int *pfds, int i_count, int i_max_count);

int exec_order;

int main(int argc, char *argv[])
{
pid_t rtn_pid, pid[3];

int rtn_error = 0;

int i, status;

int pfds[2];

int i_N = (argc > 2) ? atoi(argv[IDX_ARG_N]): 0;

exec_order = 0;

printf(“\n”);

/* create a pipe */
if (pipe(pfds) == -1) {
perror(“pipe”);
exit(1);
}else{

rtn_error = recursive_f(pfds, MAX_N, MAX_N);

}// end if

close(pfds[0]);
close(pfds[1]);

for (i = 0; i < MAX_N – 1; i++){
wait();
}

return rtn_error;
}

int recursive_f(int *pfds, int i_count, int i_max_count){

int rtn_error = 0;

char buf[MAX_BUFF];

pid_t pid;

if (DBG_LV1){

printf(“[e_o: %d][count: %d/%d] recursive_f (*pfds, %d, %d)\n”,
exec_order, i_count, i_max_count, i_count, i_max_count);

}//end if

/* fork */
if ( ( pid = fork() ) < 0) {

if (DBG_LV2)
perror(“error fork pid”);

rtn_error = 1;

}else{

/* Parent of first fork */
if (pid > 0 && i_count == i_max_count){

if (DBG_LV1)
printf(“[e_o: %d][count: %d/%d] “, exec_order, i_count, i_max_count);

printf(“Parent of first fork sending message: %s”, MSG);

rtn_error = write_pipe(pfds, MSG, MAX_BUFF, 0);

if (DBG_LV1)
printf(“[e_o: %d][count: %d/%d] “, exec_order, i_count, i_max_count);

printf(“PARENT OF FIRST FORK SENT MESSAGE: %s”, MSG);

}else{
exec_order++;

}//end if

/* Child of last fork */
if (pid == 0){

if (i_count < 1){

if (DBG_LV1)
printf(“[e_o: %d][count: %d/%d] “, exec_order, i_count, i_max_count);

printf(“Last Child of fork reading…\n”);

rtn_error = read_pipe(pfds, buf, MAX_BUFF, 5);

if (rtn_error == 0){

if (DBG_LV1)
printf(“[e_o: %d][count: %d/%d] “, exec_order, i_count, i_max_count);

printf(“LAST CHILD OF FORK READ MESSAGE: %s”, buf);

}//end if

}else{

i_count–;

if (DBG_LV1)
printf(“[e_o: %d][count: %d/%d] Calling recursive_f (i_count[%d] and i_max_count[%d]) \n”,
exec_order, i_count, i_max_count, i_count, i_max_count);

rtn_error = recursive_f(pfds, i_count, i_max_count);

}//end if

}//end if

}// end if

return rtn_error;
}

int write_pipe(int *pfds, const char *msg, int max_buff, int i_tab){

int rtn_error = 0;

/* close the read end */
close(pfds[0]);

if (DBG_LV1) printf (“%*sWRITE_PIPE: %s\n”, i_tab, ” “, msg);

/* write message to parent  through the write end */
if(write(pfds[1], msg, max_buff) <= 0) {

if (DBG_LV2) printf(“%*s[X] ERROR: Cannot write\n”, i_tab, ” “);

rtn_error = 1;

}//end if

return rtn_error;
}

int read_pipe(int *pfds, char msg[], int max_buff, int i_tab){

int rtn_error = 0;

/* close the write end */
close(pfds[1]);

if (DBG_LV1) printf (“%*sREAD_PIPE: “, i_tab, ” “);

/* read message from child through the read end */
// If not data in the pipe, the read will block
if( read(pfds[0], msg, max_buff) <= 0 ) {

if (DBG_LV2) printf ( “%*s[X] ERROR: Cannot read\n”, i_tab, ” “);

rtn_error = 1;

}else{

if (DBG_LV1) printf(“%*s%s \n”, i_tab, ” “, msg);

}//end if

return rtn_error;
}

Share
Leave a comment

How to Create a System Call

Note: Please check previous post about How to Build a Custom Kernel.

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.

  1. Prepare your system call:
    1. Go to the kernel source code folder: cd /home/your-home-folder/linux
    2. Create a personal folder: mkdir yourcall
    3. Access your folder: cd yourcall
    4. Create your source file: your_sys_call.c
    5. Create a makefile: Makefile
  2. Configure some kernel files
    1. Add your system call at the end of the file syscall_table_32.S
      1. cd /home/your-home-directory/linux/arch/x86/kernel
      2. gedit syscall_table_32.S
        iii. Add at the end of file: .long sys_your_new_system_call
    2. Add your system call at the end of the file unistd_32.h
      1. cd /home/your-home-directory/linux/x86/include/asm
      2. gedit unistd_32.h
      3. At the end of the file, add (Where XXX is the previous number plus 1)
        #define __NR_your_new_system_call XXX
    3. Increase by the number of system calls to the total system calls number: #define __NR_syscalls XXX (Where XXX is the previous number that was plus one.)
    4. Add the declaration of your system call at the end of syscalls.h
      1. cd /home/your-home-directory/linux/include/linux
      2. gedit syscalls.h
      3. asmlinkage long your_new_system_call (parameters you want to pass)
    5. Add the new folder to the kernel compile’s Makefile
      core-y += /kernel ... other folder... /yoursyscall
      
      
  3. Configure your system call
    1. Write your system call, inside yoursyscall.c
      asmlinkage long new_system_call (whatever params you want to pass){
      // whatever you want to do
      }
    2. Change the makefile by adding the following line: obj-y := yoursyscall.o
    3. Compile your kernel (Follow steps at Building a New Custom Kernel
  4. Test your system call
    1. Create a user level program that calls your system call
    2. Create a header file that the user space program can use:
      /* header.h */
      #include < linux/unistd.h >
      #define __NR_new_system_call XXX
      
      /* if you system call returns int and takes no parameter
      * use this macro
      */
      _syscall0(int,new_system_call)
      
      /* Otherwise, depending on the number of parameters
      * being passed use the _syscallN macro, N being the no
      * of params, like
      _syscall1(int, new_system_call, int)
      */
  5. Starting at kernel 2.6.18, the _syscallXX macros were removed from the header files to user space, therefore syscall() functions is required to use:
    1. printf (“System call returned %d \n”, syscall (__NR_new_system_call, params_if_any));
    2. or change the header.h file:
      * header.h */
      #include < linux/unistd.h >
      #include < sys/syscall.h >
      #define __NR_new_system_call XXX
      
      long new_system_call (params_if_any){
         return syscall (__NR_new_system_call, params_if_any);
      }
  6. Test the code:
    /* test client */
    #include 'header.h'
    
    int main (void){
        printf ('System call returned %d \n', new_system_call());
        return 1;
    }

NEW!!!

Before you do update-grub (if using , do the following command line (Where x.x.xx is the kernel version you compiled):

sudo update-initramfs -c -k x.x.xx

After Ubuntu 10.04 (or kernel 2.6.32) this seems to be a needed extra step to make it work.

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

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

Example of Disjktra 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 Disjktra algorithm using heap.

disjktra_heap.c:

/*
 * Program: 09
 * Author: Alejandro G. Carlstein
 * Description: Disjktra Algorithm using heap
 */

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

#define MAX_EDGES 100001
#define MAX_VERTICES  500001
#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 startVertex;
  int endVertex;
  unsigned int length;
} edges[MAX_EDGES];

struct Vertex{
	unsigned int id;
	unsigned int weight;
	struct Vertex *predecessor;
	short visited;
} vertices[MAX_VERTICES];

struct AdjList{
	struct Vertex *vertexPointer;
	int edgeIndex;
	struct AdjList *next;
} *adjList[MAX_VERTICES], *headAdj, *newAdj;

void init(void);
void readStandardInput(void);
void printEdges(void);
void disjktraAlgorithm(void);
void initializeSingleSource(void);
void printVertices(void);
void buildAdjacentVertexList(void);
void insertAdjVerticesOf(int vertexIndex);
void insertAdjVertex(int vertexIndex, int adjVertexIndex, int edgeIndex);
void printAdjList(int vertexIndex);
void makePriorityQueue(int heapArray[], int *length);
void printArray(int array[], int length);
void buildMinHeap(int heapArray[], int length);
void minHeapify(int heapArray[], int index, int heapSize);
int heapExtractMin(int heapArray[], int *heapSize);
void exchange(int *a, int *b);
void addVertexToList(struct AdjList *vertexList, struct Vertex *vertex);
void relax(int startVertex, int endVertex, int edge);
void printRoute(void);
void debug(int debugLevel, char *fmt, ...);
void errorDoExit(char *fmt, ...);

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

	init();
	disjktraAlgorithm();
	printVertices();
	return 0;
}

void init(void){
	debug(DBG_LV0, 'init()');
	readStandardInput();
}

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

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

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

	int i;
	for(i = 0; i < numEdges; ++i){
		scanf('%d %d %d', &edges[i].startVertex, &edges[i].endVertex, &edges[i].length);
		debug(DBG_LV1, '[%d](%d <%d> %d)', i, edges[i].startVertex, edges[i].length, edges[i].endVertex);
	}
}

// Disjktra(G, w, s)	//s is source vertex - w is weight
void disjktraAlgorithm(void){
	debug(DBG_LV0, 'disjktraAlgorithm()');	

	// InitializeSingleSource(G, s);
	initializeSingleSource();

	//	S <- 0    // It will hold vertices
	struct AdjList *vertexList = NULL;

	//	Q <- V[G] // Make a priority Queue for the vertices
	int heapArray[numVertices];
	int heapLength = 0;
	makePriorityQueue(heapArray, &heapLength);

	//	while Q != 0
	while(heapLength > 0){	

		//		do u <- extractMin(Q)
		if (DBG_LV1) printArray(heapArray, heapLength);
		int vertexIndex = heapExtractMin(heapArray, &heapLength);
		debug(DBG_LV1, '[!]vertex[%d] Weight: %d\n', vertexIndex, vertices[vertexIndex].weight);
		if (DBG_LV1) printArray(heapArray, heapLength);		

		//S <- S U {u}
		addVertexToList(vertexList, &vertices[vertexIndex]);

		//		for each vertex v e Adj[u]
		struct AdjList *tempAdj;
		tempAdj = adjList[vertexIndex];
		while(tempAdj != NULL){
			//			do relax(u, v, w);
			relax(vertexIndex, tempAdj->vertexPointer->id, tempAdj->edgeIndex);
			tempAdj = tempAdj->next;
		}
		vertices[vertexIndex].visited = TRUE;
	}

}	

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

	int i;
	for(i = 0; i < numVertices; ++i){
		vertices[i].id = i;
		vertices[i].weight = INT_MAX;
		vertices[i].predecessor = NULL;	// p[v] predecessor that is either another vertex or NULL
		vertices[i].visited = FALSE;
	}
	vertices[0].weight = 0;

	if (DBG_LV1) printVertices();

	buildAdjacentVertexList();	

	if (DBG_LV1){
		debug(DBG_LV1, '*List of all adj. vertices*');
		for (i = 0; i < numVertices; ++i)
			printAdjList(i);
	}

}

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

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

	if (DBG_LV1){
		printf('\n[i]');
		for (i = 0; i < numVertices; ++i)
			printf(' %d ' , vertices[i].id);
	}

	printf('\n[W]');
	for (i = 0; i < numVertices; ++i)
		if (vertices[i].weight == INT_MAX){
			printf(' ! ');
		}else{
			printf(' %d ' , vertices[i].weight);
		}

	if(DBG_LV1){
		printf('\n[*]');
		for (i = 0; i < numVertices; ++i)
			if (vertices[i].predecessor == NULL){
				printf(' N ');
			}else{
				printf(' %d ' , (int)vertices[i].predecessor->id);
			}
	}

	if(DBG_LV1){
		printf('\n[V]');
		for (i = 0; i < numVertices; ++i)
			if (vertices[i].visited == TRUE){
				printf(' Y ');
			}else{
				printf(' N ');
			}
	}

	printf('\n');
}

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

	int vertexIndex;
	for (vertexIndex = 0; vertexIndex < numVertices; ++vertexIndex){
		insertAdjVerticesOf(vertexIndex);
	}
}

void insertAdjVerticesOf(int vertexIndex){
	debug(DBG_LV0, 'insertAdjVerticesOf(vertexIndex: %d)', vertexIndex);	

	debug(DBG_LV1, ' Searching for adjacent Vertices');
	int edgeIndex;
	for (edgeIndex = 0; edgeIndex < numEdges; ++edgeIndex){

		int startVertex = edges[edgeIndex].startVertex;
		int endVertex = edges[edgeIndex].endVertex;
		debug(DBG_LV1, '  Edge[%d](%d <%d> %d)', edgeIndex, startVertex, edges[edgeIndex].length, endVertex);

		debug(DBG_LV1, '  (startVertex (%d) == (%d) vertexIndex)?', startVertex, vertexIndex);
		if (startVertex == vertexIndex){
			debug(DBG_LV1, '   YES');
			insertAdjVertex(vertexIndex, endVertex, edgeIndex);
			insertAdjVertex(endVertex, vertexIndex, edgeIndex);
		}
	}
	if(DBG_LV1) printAdjList(vertexIndex);
}

void insertAdjVertex(int vertexIndex, int adjVertexIndex, int edgeIndex){

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

	struct AdjList *newAdj = (struct AdjList *) malloc(sizeof(struct AdjList));
	newAdj->vertexPointer = &vertices[adjVertexIndex];
	newAdj->edgeIndex = edgeIndex;
	newAdj->next = NULL;

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

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

	debug(DBG_LV1, 'Adjacent Vertices of Vertex: %d', vertexIndex);

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

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

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

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

		printf('\n[W]');
		tempAdj = adjList[vertexIndex];
		while(tempAdj != NULL){
			if (tempAdj->vertexPointer->weight == INT_MAX){
				printf(' ! ');
			}else{
				printf(' %d ' , tempAdj->vertexPointer->weight);
			}
			tempAdj = tempAdj->next;
		}

		printf('\n[*]');
		tempAdj = adjList[vertexIndex];
		while(tempAdj != NULL){
			if (tempAdj->vertexPointer->predecessor == NULL){
				printf(' N ');
			}else{
				printf(' %d ' , tempAdj->vertexPointer->predecessor->id);
			}
			tempAdj = tempAdj->next;
		}

		printf('\n[V]');
		tempAdj = adjList[vertexIndex];
		while(tempAdj != NULL){
			if (tempAdj->vertexPointer->visited == TRUE){
				printf(' Y ');
			}else{
				printf(' N ');
			}
			tempAdj = tempAdj->next;
		}

		printf('\n');
	}
}

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

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

	*length = numVertices;
	if (DBG_LV1) printArray(heapArray, *length);
	buildMinHeap(heapArray, *length);
	if (DBG_LV1) printArray(heapArray, *length);
	if (DBG_LV1) printVertices();
}

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 buildMinHeap(int heapArray[], int length){
	debug(DBG_LV0, 'buildMinHeap(length: %d)', length);

	int heapSize = length;

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

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

	int smallestIndex = index;
	int leftIndex = LEFT(index);
	int rightIndex = RIGHT(index);
	debug(DBG_LV1, '-SmallestIndex: %d, leftIndex: %d, rightIndex: %d', smallestIndex, leftIndex, rightIndex);

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

		unsigned int indexValue = vertices[heapArray[index]].weight;
		debug(DBG_LV1,
					'INDEX: vertices[heapArray[%d]: %d].id: %d, .weight: %d',
					index, heapArray[index], vertices[heapArray[index]].id,
					indexValue);

		unsigned int leftValue = vertices[heapArray[leftIndex]].weight;
		debug(DBG_LV1,
					'LEFT VALUE: vertices[heapArray[%d]: %d].id: %d, .weight: %d',
					leftIndex, heapArray[leftIndex], vertices[heapArray[leftIndex]].id,
					leftValue);

		if ((leftIndex < heapSize) && (leftValue < indexValue))
			smallestIndex = leftIndex;

		debug(DBG_LV1, 'smallestIndex: %d', smallestIndex);

		unsigned int rightValue = vertices[heapArray[rightIndex]].weight;

		debug(DBG_LV1,
					'LEFT VALUE: vertices[heapArray[%d]: %d].id: %d, .weight: %d',
					rightIndex, heapArray[rightIndex], vertices[heapArray[rightIndex]].id,
					rightValue);

		if ((rightIndex < heapSize) && (rightValue < indexValue))
			smallestIndex = rightIndex;

		debug(DBG_LV1, 'smallestIndex: %d', smallestIndex);

		if (smallestIndex != index){
			exchange(&heapArray[index], &heapArray[smallestIndex]);
			minHeapify(heapArray, smallestIndex, heapSize);
		}
	}
}

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

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

	buildMinHeap(heapArray, *heapSize);

	int min = heapArray[0];
	--*heapSize;
	heapArray[0] = heapArray[*heapSize];
	minHeapify(heapArray, 1, *heapSize);

	return min;
}

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 addVertexToList(struct AdjList *vertexList, struct Vertex *vertex){
	debug(DBG_LV0, 'addVertexToList()');	

	struct AdjList *newAdj = (struct AdjList *) malloc(sizeof(struct AdjList));
	newAdj->vertexPointer = vertex;
	if (vertexList == NULL){
		newAdj->next = vertexList;
		vertexList = newAdj;
	}else{
		struct AdjList *currentAdj = vertexList;
		while (currentAdj->next != NULL)
			currentAdj = currentAdj->next;
		newAdj->next = currentAdj->next;
		currentAdj->next = newAdj;
	}
}

void relax(int startVertex, int endVertex, int edgeIndex){
	debug(DBG_LV0, 'relax(startVertex: %d, endVerted: %d, edgeIndex: %d)', startVertex, endVertex, edgeIndex);	

	unsigned int weight = vertices[startVertex].weight + edges[edgeIndex].length;

	debug (DBG_LV1, 'vertices[%d].weight(%d) > (%d)weight', endVertex, vertices[endVertex].weight, weight);
	if (vertices[endVertex].weight > weight){
		vertices[endVertex].weight = weight;
		vertices[endVertex].predecessor = &vertices[startVertex];
	}
}	

void debug(int debugLevel, char *fmt, ...){
	if (debugLevel){
		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:

8 11
0 1 1
4 5 1
1 5 2
2 5 2
5 6 2
0 3 2
3 4 3
5 7 3
4 2 4
4 6 4
1 2 5

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

Example of Kurskay’s Algorithm using Disjoint Sets and 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 Kurskay’s algorithm using disjoint sets and heap.

kurskay_djoinset_heap.c:

/*
 * Program: 08
 * Author: Alejandro G. Carlstein
 * Description: Applying Kurskay's Algorithm using Disjoint Sets
 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <malloc.h>

#define MAX_EDGES 100001
#define MAX_VERTICES  500001
#define MAX_HEAP 100001
#define LEFT(i) ((i << 1) + 1)
#define RIGHT(i) ((i << 1) + 2)
#define PARENT(i) (((i + 1) >> 1) - 1)
#define DIV_BY_2(i) (i >> 1)
#define ROOT_INDEX 0

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

struct Vertex{
	int id;
	int rank;
	struct Vertex *parent;
};

struct Edge{
  struct Vertex *startVertex;
  struct Vertex *endVertex;
  int length;
};

struct Edge edges[MAX_EDGES];
struct Vertex vertices[MAX_VERTICES];
int heap[MAX_EDGES];

void scanEdges(void);
void debug(const char *message, int isDebugging);
void printEdges(struct Edge edges[], int length);
void initHeap(void);
int *mstKruskal(int *numEdges);
void printVertices(struct Vertex vertices[]);
void heapSort(int array[], int length);
void buildMinHeap(int array[], int heapSize);
void minHeapify(int array[], int index, int heapSize);
void exchange(int *a, int *b);
void printArray(int array[], int length);
void makeSet(struct Vertex *vertex);
struct Vertex* findSet(struct Vertex *vertex);
void unionTrees(struct Vertex *vertexX, struct Vertex *vertexY);
void link(struct Vertex *vertexX, struct Vertex *vertexY);
void printEdgesUsingHeapArray(int heapArray[], int length);
void printWeightOfTree(int heapArray[], int length);

int numVertices;
int numEdges;

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

	scanEdges();
	initHeap();
	int length = numEdges;
 	int *arrayHeapEdges;
 	arrayHeapEdges = mstKruskal(&length);

 	if (DBG_LV1) printArray(arrayHeapEdges, length);

 	if(DBG_LV1) printVertices(vertices);

	if (DBG_LV1) printEdgesUsingHeapArray(arrayHeapEdges, length);		

	printWeightOfTree(arrayHeapEdges, length);

	free(arrayHeapEdges);

	return 0;

}

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

	scanf('%d %d', &numVertices, &numEdges);

	if (DBG_LV1) printf('numVertices: %d, numEdges: %d\n', numVertices, numEdges);

	int i;
	int startVertexId = -1;
	int endVertexId = -1;
	for (i = 0;
			 scanf('%d %d %d', &startVertexId, &endVertexId, &edges[i].length) == 1 ||
			 			 i < numEdges;
			 ++i){

		if (DBG_LV2)
			printf('startVertexId: %d, endVertexId: %d\n', startVertexId, endVertexId);

		if (startVertexId >= numVertices ||
				endVertexId >= numVertices){
			fprintf(stderr, 'Error: Vertex id is outside the maximum range of vertices\n');
			exit(1);
		}

		vertices[startVertexId].id = startVertexId;
		edges[i].startVertex = &vertices[startVertexId];

		vertices[endVertexId].id = endVertexId;
		edges[i].endVertex = &vertices[endVertexId];

		if(DBG_LV2)
			printf('edges[%d].startVertex->id: %d, edges[%d].endVertex->id: %d\n',
						 i, edges[i].startVertex->id, i, edges[i].endVertex->id);

	}

	if (DBG_LV1)
		printEdges(edges, numEdges);

}

void debug(const char *message, int isDebugging){
	if (isDebugging) printf('%s\n', message);
}

void printEdges(struct Edge edges[], int length){
	debug('printEdges()', DBG_LV0);

	printf('Edges: \n');
	int i;
	for (i = 0; i < length; ++i)
		printf('%d(%d <%d> %d) ',
					 i, edges[i].startVertex->id, edges[i].length, edges[i].endVertex->id);

		printf('\n');
}

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

	int i;

	for (i = 0; i < numEdges; ++i)
		heap[i] = i;
}

int *mstKruskal(int *numEdges){
	debug('mstKruskal()', DBG_LV0);	

	// A <- 0
	int *arrayEdgesIndex = (int*) malloc(*numEdges * sizeof(int));

	int vertexIndex;
	for (vertexIndex = 0; vertexIndex < numVertices; ++vertexIndex)
		makeSet(&vertices[vertexIndex]);

	if (DBG_LV1) printVertices(vertices);

	// Sort edges into nondecreasing order by weight
	heapSort(heap, *numEdges);

	int index = 0;
	int edgeIndex;
	for (edgeIndex = 0; edgeIndex < *numEdges; ++edgeIndex){

		if (DBG_LV2)
			printf('V: %d\n', (int)findSet(edges[heap[edgeIndex]].startVertex));

		if ((int)findSet(edges[heap[edgeIndex]].startVertex) !=
				(int)findSet(edges[heap[edgeIndex]].endVertex)  ){

			if (DBG_LV2)
				printf('findset(edges[%d]) = findset(edges[%d])\n',
							 heap[edgeIndex], heap[edgeIndex]);

			// A <- A U {(u,v)}
			arrayEdgesIndex[index++] = heap[edgeIndex];	

			unionTrees(edges[heap[edgeIndex]].startVertex,
								 edges[heap[edgeIndex]].endVertex);
		}

	}

	*numEdges = index;

	if (DBG_LV1) printArray(arrayEdgesIndex, index);

	return (arrayEdgesIndex);
}

void printVertices(struct Vertex vertices[]){
	debug('printVertices()', DBG_LV0);

	int i;
	for (i = 0; i < numVertices; ++i)
		printf('(%d)[%d] Id: %d, Rank: %d, *Parent:%d \n',
					 (int)&vertices[i], i, vertices[i].id, vertices[i].rank, (int)vertices[i].parent);

	printf('\n');
}

void heapSort(int array[], int length){
	if (DBG_LV0) printf('heapSort(length: %d)\n', length);

	buildMinHeap(array, length);

	int i;
	int	heap_size = length;
	for (i = length - 1 ; i >= 0; --i){
		exchange(&array[0], &array[i]);
		heap_size--;
		minHeapify(array, 0, heap_size);
	}

}

void buildMinHeap(int array[], int heapSize){
	debug('buildMinHeap', DBG_LV0);

	int index;
	for (index = DIV_BY_2(heapSize); index >= ROOT_INDEX; --index)
		minHeapify(array, index, heapSize);
}

void minHeapify(int array[], int index, int heapSize){
	debug('minHeapify()', DBG_LV0);

	int left, right, smallest;

	smallest = index;
	left = LEFT(index);
	right = RIGHT(index);	

	if (left < heapSize &&
		  edges[array[left]].length > edges[array[index]].length)
		smallest = left;	

	if (right < heapSize &&
		  edges[array[right]].length > edges[array[smallest]].length)
		smallest = right;

	if (smallest != index){
		exchange(&array[index], &array[smallest]);
		minHeapify(array, smallest, heapSize);
	}

}

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

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

void makeSet(struct Vertex *vertex){
	debug('makeSet()', DBG_LV0);

	vertex->parent = vertex;
	vertex->rank = 0;
}

struct Vertex* findSet(struct Vertex *vertex){
	debug('findSet()', DBG_LV0);

	if (vertex == NULL)
		debug('Vertex is NULL', DBG_LV1);

	if (vertex != vertex->parent){
		vertex->parent = findSet(vertex->parent);
	}	

	return (vertex->parent);
}

void unionTrees(struct Vertex *vertexX, struct Vertex *vertexY){
	debug('unionTrees()', DBG_LV0);

	link(findSet(vertexX), findSet(vertexY));
}

void link(struct Vertex *vertexX, struct Vertex *vertexY){
	debug('link()', DBG_LV0);

	if (vertexX->rank > vertexY->rank){
		vertexY->parent = vertexX;
	}else{
		vertexX->parent = vertexY;
		if (vertexX->rank == vertexY->rank)
			++vertexY->rank;
	}

}

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

	int i;

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

	printf('\n');

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

	if (DBG_LV1) printf('\n\n');
}

void printEdgesUsingHeapArray(int heapArray[], int length){
	debug('printEdgesUsingHeapArray()', DBG_LV0);

	int i;
	for (i = 0; i < length; ++i)
		printf('%d-%d(%d) ',
					 edges[heapArray[i]].startVertex->id, edges[heapArray[i]].endVertex->id, (i + 1));
}

void printWeightOfTree(int heapArray[], int length){
	debug('printWeightOfTree()', DBG_LV0);

	int result = 0;
	int i;
	for (i = 0; i < length; ++i)
		result += edges[heapArray[i]].length;

	printf('%d\n', result);

}

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