Program Code
/*
Using the priority queue implement Dijkstra's Single source shortest path in a weighted graph.
Consider the edge weights to be non-negetive.
*/
Sample Input .CSV File can be found Here.
Program Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*Defining the Macros for using in Dijkstra Algo*/
#define INFINITY 98964
#define UNDEFINED -1
/*Defining the HEAP Node structer*/
typedef struct heap_node{
int vertex;
int vertex_weight;
struct heap_node* parent;
struct heap_node* left_child;
struct heap_node* right_child;
struct heap_node* next_node;
struct heap_node* prev_node;
} heap_node;
/*Defining the edge structer for the Adj link list*/
typedef struct adj_list_edge{
int vertex;
int weight;
struct adj_list_edge* next;
} adj_list_edge;
/*Defining the structer for the Adj link list*/
typedef struct adj_list{
struct adj_list_edge* head;
}adj_list;
/*Defining the structer for the Graph*/
typedef struct graph
{
int no_vertex;
struct adj_list* array;
}graph;
/*Declaration of functions*/
void insert_into_pqueue(heap_node** start, heap_node** end, heap_node** prev, heap_node** comp, int vertex, int weight);
int dequeue_from_pqueue(heap_node** start, heap_node** end, heap_node** prev, heap_node** comp);
void decrease_priority(heap_node** start, heap_node** comp, int value_v, int alt);
void display_priority_queue(heap_node* start);
void heapify_down(heap_node** comp);
void heapify_up(heap_node** start, heap_node** comp);
struct graph* create_graph(int vertex);
void insert_edge(struct graph* graph, int node, int vertex, int weight);
void display_adj_list(struct graph* graph);
/*Starting of the Main Function*/
int main()
{
heap_node* start = NULL;
heap_node* end = NULL;
heap_node* prev = NULL;
heap_node* comp = NULL;
int choice, value_u, value_v, alt, source;
const char filename[] = "Graph_adj_list.csv";
char buffer[BUFSIZ], *ptr, *ptr_in, b[BUFSIZ];
int arr_v[100] = {0};
int arr_w[100] = {0};
size_t i, j, k, node_count, node_src, node_dest;
int *dist, *previous, *flag;
/*File Pointers to read the Adjcency List file.*/
FILE *file_pointer;
/* Count number of lines in Adj List CVS file.*/
file_pointer = fopen(filename, "r");
if ( file_pointer )
{
for ( node_count = 0; fgets(buffer, sizeof buffer, file_pointer); ++node_count )
{ }
}
else /* fopen() returned NULL */
{
perror(filename);
}
fclose(file_pointer);
printf("\n\nNumber of Nodes in the Graph: %d\n", node_count);
struct graph* graph = create_graph(node_count);
/* Reading the vertex weights from the file and storing it in "Graph Structure".*/
file_pointer = fopen(filename, "r");
if ( file_pointer )
{
/*Read each token/vertex value from the line*/
for ( i = 0; fgets(buffer, sizeof buffer, file_pointer); ++i )
{
j=0;
ptr = (char *)strtok(buffer, "->");
node_src = strtol(ptr, (char **)NULL, 10);
node_src--;
ptr = (char *)strtok(NULL,"->");
while(ptr!=NULL)
{
strcpy(b ,ptr);
ptr_in = b;
arr_v[j] = (int)strtol(ptr_in, &ptr_in, 10);
++ptr_in;
arr_w[j] = (int)strtol(ptr_in, (char **)NULL, 10);
j++;
ptr = (char *)strtok(NULL,"->");
}
while(j>0)
{
if(arr_v[j-1]!=0)
insert_edge( graph, node_src, arr_v[j-1], arr_w[j-1]);
j--;
}
}
}
else /* fopen() returned NULL */
{
perror(filename);
}
fclose(file_pointer);
/*Display the Graph Adj list*/
printf("\n******************************\n\tGraph Adj List \n******************************");
display_adj_list(graph);
printf("\n\n");
/************************************************
****CODE FOR Dijkstra_algorithm****
*************************************************/
dist = (int *)malloc(node_count * sizeof(int));
previous = (int *)malloc(node_count * sizeof(int));
flag = (int *)malloc(node_count * sizeof(int));
for (i=0; i<node_count; ++i)
{
dist[i] = INFINITY;
previous[i] = UNDEFINED;
flag[i] = 0;
}
while(1)
{
printf("Enter the Source Node in the Graph: ");
scanf("%d", &source);
if(source <= node_count && source > 0 )
break;
printf("Error : Source Node does not exist in the Graph.\n\n");
}
dist[source-1] = 0;
previous[source-1] = -1;
for( i=0; i<node_count; ++i)
{
insert_into_pqueue( &start, &end, &prev, &comp, i+1, dist[i] );
heapify_down(&comp);
}
printf("\nPriority Queue After Initializations.\n");
printf("*************************************\n");
display_priority_queue(start);
while(1)
{
value_u = dequeue_from_pqueue(&start, &end, &prev, &comp);
heapify_up(&start, &comp);
if (value_u == -1)
{ break; }
value_u--;
flag[value_u] = 1;
struct adj_list_edge* temp;
temp = graph->array[value_u].head;
while(temp)
{
value_v = temp->vertex;
value_v--;
if( flag[value_v] == 0)
{
alt = dist[value_u] + temp->weight;
if( alt < dist[value_v] )
{
dist[value_v] = alt;
previous[value_v] = value_u+1;
value_v++;
decrease_priority(&start, &comp, value_v, alt );
heapify_down(&comp);
}
}
temp = temp->next;
}
}
/*Displaying the final results*/
printf("\nSource Destination Cost Path\n");
for(i=0; i<node_count; ++i)
{
printf(" %d ", source);
printf(" %d ", i+1);
if(dist[i]<INFINITY)
{ printf(" %d ", dist[i]); }
else
{ printf(" INFINITY "); }
if((i+1)==source)
{ printf("[ %d ]\n",source); }
else if(dist[i]==INFINITY)
{ printf("\n"); }
else
{ k=0;
j=i;
arr_v[k]=j+1;
k++;
while((j+1) != source)
{
arr_v[k]=previous[j];
j = previous[j]-1;
k++;
}
printf("[ %d", arr_v[k-1]);
for(j=k-1; j>0; j--)
{
printf("->%d", arr_v[j-1]);
}
printf(" ]\n");
}
}
return 0;
}
/*End of the main program*/
/*************************/
/*Function defination to create a graph with ajd lists*/
struct graph* create_graph(int vertex)
{
struct graph* g = (struct graph*) malloc(sizeof(struct graph));
g->no_vertex = vertex;
/*Allocate memory for the adj lists*/
g->array = (struct adj_list*) malloc(vertex * sizeof(struct adj_list));
/*Init the head of each ajd list head with NULL*/
while(vertex>0)
{
g->array[vertex-1].head = NULL;
vertex--;
}
return g;
}
/*Insert edge node in to a given adj list in the graph structure*/
void insert_edge(struct graph* graph, int node, int vertex, int weight)
{
struct adj_list_edge* new_edge = (struct adj_list_edge*) malloc(sizeof(struct adj_list_edge));
new_edge->vertex = vertex;
new_edge->weight = weight;
new_edge->next = NULL;
new_edge->next = graph->array[node].head;
graph->array[node].head = new_edge;
}
/*Function Defination for displaying the Graph adj list */
void display_adj_list(struct graph* graph)
{
int i;
for (i=0; i<graph->no_vertex; ++i)
{
struct adj_list_edge* temp;
temp = graph->array[i].head;
printf("\n Adjacency list of vertex %d\n head ", i+1);
while(temp)
{
printf("-> %d/%d", temp->vertex, temp->weight);
temp = temp->next;
}
printf("\n");
}
}
/*Function defination to insert the node into the heap*/
void insert_into_pqueue(heap_node** start, heap_node** end, heap_node** prev, heap_node** comp, int vertex, int weight)
{
heap_node* temp_node = NULL;
temp_node = (heap_node*) malloc(sizeof(heap_node));
if (temp_node == NULL)
{
printf("Memory for Heap Node can't be allocated");
exit(0);
}
temp_node->vertex = vertex;
temp_node->vertex_weight = weight;
/*If there is no elements in the Heap */
if(*end == NULL)
{
*start = temp_node;
*end = temp_node;
*prev = temp_node;
*comp = temp_node;
/*Init the pointers with NULL Values*/
temp_node->parent = NULL;
temp_node->left_child = NULL;
temp_node->right_child = NULL;
temp_node->next_node = NULL;
temp_node->prev_node = NULL;
}
else /*If the Heap is already having nodes it it*/
{
if((*end)->left_child == NULL)
{
(*end)->left_child = temp_node;
/*Manupulating the pointers values*/
temp_node->parent = *end;
temp_node->left_child = NULL;
temp_node->right_child = NULL;
temp_node->next_node = NULL;
temp_node->prev_node = *prev;
(*prev)->next_node = temp_node;
*prev = temp_node;
*comp = temp_node;
}
else
{
(*end)->right_child = temp_node;
/*Manupulating the pointers values*/
temp_node->parent = *end;
temp_node->left_child = NULL;
temp_node->right_child = NULL;
temp_node->next_node = NULL;
temp_node->prev_node = *prev;
(*prev)->next_node = temp_node;
*prev = temp_node;
*comp = temp_node;
*end = (*end)->next_node;
}
}
}
/*Function defination of delete from Priority Queue*/
int dequeue_from_pqueue(heap_node** start, heap_node** end, heap_node** prev, heap_node** comp)
{
int element = -1;
if(*start == NULL)
{
return element;
}
element = (*start)->vertex;
if((*start)->left_child == NULL)
{
free(*start);
*start = NULL;
*end = NULL;
*prev = NULL;
*comp = NULL;
}
else
{
if((*end)->left_child == NULL)
{
(*start)->vertex_weight = (*prev)->vertex_weight;
(*start)->vertex = (*prev)->vertex;
*end = (*end)->prev_node;
(*end)->right_child = NULL;
*comp = *prev;
*prev = (*prev)->prev_node;
(*prev)->next_node = NULL;
free(*comp);
*comp = *prev;
}
else
{
(*start)->vertex_weight = (*prev)->vertex_weight;
(*start)->vertex = (*prev)->vertex;
(*end)->left_child = NULL;
*comp = *prev;
*prev = (*prev)->prev_node;
(*prev)->next_node = NULL;
free(*comp);
*comp = *prev;
}
}
return element;
}
/*Function defination to decrease priority of a node in the Priority Queue*/
void decrease_priority(heap_node** start, heap_node** comp, int value_v, int alt)
{
int i;
*comp = *start;
while(1)
{
if(*comp == NULL) break;
if((*comp)->vertex == value_v)
{
(*comp)->vertex_weight = alt;
return;
}
*comp = (*comp)->next_node;
}
}
/*Function defination to diplay the Priority Queue*/
void display_priority_queue(heap_node* start)
{
if(start == NULL)
{
printf("Queue is empty...\n\n");
return;
}
heap_node* temp_start = start;
while(1)
{
if(temp_start == NULL)break;
printf("%d", temp_start->vertex,temp_start->vertex_weight);
if(temp_start->vertex_weight == INFINITY)
printf("/INFY ");
else
printf("/%d ", temp_start->vertex_weight);
temp_start = temp_start->next_node;
}
printf("\n\n");
}
/*Function defination to heapify the heap from down*/
void heapify_down(heap_node** comp)
{
int i, j;
while((*comp)->parent != NULL)
{
heap_node* temp_parent = (*comp)->parent;
if( (*comp)->vertex_weight < temp_parent->vertex_weight )
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_parent->vertex_weight;
(*comp)->vertex = temp_parent->vertex;
*comp = (*comp)->parent;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
}
else
{ break; }
}
}
/*Function defination to heapify the heap from down*/
void heapify_up(heap_node** start, heap_node** comp)
{
int i, j;
*comp = *start;
/*If No node is there in Heap*/
if(*start == NULL)
{ return; }
/*If just in one node is there in the Heap*/
if((*comp)->left_child == NULL && (*comp)->right_child == NULL)
{ return; }
/*If only two nodes are there in the Heap*/
if((*comp)->right_child == NULL)
{
heap_node* temp_child = (*comp)->left_child;
if((*comp)->vertex_weight > temp_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_child->vertex_weight;
(*comp)->vertex = temp_child->vertex;
*comp = (*comp)->left_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
}
return;
}
/*If more than two nodes are there in the Heap*/
while((*comp)->left_child != NULL || (*comp)->right_child != NULL )
{
if((*comp)->right_child == NULL)
{
heap_node* temp_left_child = (*comp)->left_child;
if((*comp)->vertex_weight >= temp_left_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_left_child->vertex_weight;
(*comp)->vertex = temp_left_child->vertex;
*comp = (*comp)->left_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
}
return;
}
else
{
heap_node* temp_left_child = (*comp)->left_child;
heap_node* temp_right_child = (*comp)->right_child;
if(temp_left_child->vertex_weight == temp_right_child->vertex_weight)
{
if((*comp)->vertex_weight <= temp_left_child->vertex_weight)
{
return;
}
if((*comp)->vertex_weight > temp_left_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_left_child->vertex_weight;
(*comp)->vertex = temp_left_child->vertex;
*comp = (*comp)->left_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
continue;
}
}
else if(temp_left_child->vertex_weight < temp_right_child->vertex_weight)
{
if((*comp)->vertex_weight <= temp_left_child->vertex_weight)
{
return;
}
else if((*comp)->vertex_weight > temp_left_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_left_child->vertex_weight;
(*comp)->vertex = temp_left_child->vertex;
*comp = (*comp)->left_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
continue;
}
}
else
{
if((*comp)->vertex_weight <= temp_right_child->vertex_weight)
{
return;
}
if((*comp)->vertex_weight > temp_right_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_right_child->vertex_weight;
(*comp)->vertex = temp_right_child->vertex;
*comp = (*comp)->right_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
continue;
}
}
}
}
}
/*******************************
END OF THE PROGRAM
********************************/
/*
Using the priority queue implement Dijkstra's Single source shortest path in a weighted graph.
Consider the edge weights to be non-negetive.
*/
Sample Input .CSV File can be found Here.
Program Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*Defining the Macros for using in Dijkstra Algo*/
#define INFINITY 98964
#define UNDEFINED -1
/*Defining the HEAP Node structer*/
typedef struct heap_node{
int vertex;
int vertex_weight;
struct heap_node* parent;
struct heap_node* left_child;
struct heap_node* right_child;
struct heap_node* next_node;
struct heap_node* prev_node;
} heap_node;
/*Defining the edge structer for the Adj link list*/
typedef struct adj_list_edge{
int vertex;
int weight;
struct adj_list_edge* next;
} adj_list_edge;
/*Defining the structer for the Adj link list*/
typedef struct adj_list{
struct adj_list_edge* head;
}adj_list;
/*Defining the structer for the Graph*/
typedef struct graph
{
int no_vertex;
struct adj_list* array;
}graph;
/*Declaration of functions*/
void insert_into_pqueue(heap_node** start, heap_node** end, heap_node** prev, heap_node** comp, int vertex, int weight);
int dequeue_from_pqueue(heap_node** start, heap_node** end, heap_node** prev, heap_node** comp);
void decrease_priority(heap_node** start, heap_node** comp, int value_v, int alt);
void display_priority_queue(heap_node* start);
void heapify_down(heap_node** comp);
void heapify_up(heap_node** start, heap_node** comp);
struct graph* create_graph(int vertex);
void insert_edge(struct graph* graph, int node, int vertex, int weight);
void display_adj_list(struct graph* graph);
/*Starting of the Main Function*/
int main()
{
heap_node* start = NULL;
heap_node* end = NULL;
heap_node* prev = NULL;
heap_node* comp = NULL;
int choice, value_u, value_v, alt, source;
const char filename[] = "Graph_adj_list.csv";
char buffer[BUFSIZ], *ptr, *ptr_in, b[BUFSIZ];
int arr_v[100] = {0};
int arr_w[100] = {0};
size_t i, j, k, node_count, node_src, node_dest;
int *dist, *previous, *flag;
/*File Pointers to read the Adjcency List file.*/
FILE *file_pointer;
/* Count number of lines in Adj List CVS file.*/
file_pointer = fopen(filename, "r");
if ( file_pointer )
{
for ( node_count = 0; fgets(buffer, sizeof buffer, file_pointer); ++node_count )
{ }
}
else /* fopen() returned NULL */
{
perror(filename);
}
fclose(file_pointer);
printf("\n\nNumber of Nodes in the Graph: %d\n", node_count);
struct graph* graph = create_graph(node_count);
/* Reading the vertex weights from the file and storing it in "Graph Structure".*/
file_pointer = fopen(filename, "r");
if ( file_pointer )
{
/*Read each token/vertex value from the line*/
for ( i = 0; fgets(buffer, sizeof buffer, file_pointer); ++i )
{
j=0;
ptr = (char *)strtok(buffer, "->");
node_src = strtol(ptr, (char **)NULL, 10);
node_src--;
ptr = (char *)strtok(NULL,"->");
while(ptr!=NULL)
{
strcpy(b ,ptr);
ptr_in = b;
arr_v[j] = (int)strtol(ptr_in, &ptr_in, 10);
++ptr_in;
arr_w[j] = (int)strtol(ptr_in, (char **)NULL, 10);
j++;
ptr = (char *)strtok(NULL,"->");
}
while(j>0)
{
if(arr_v[j-1]!=0)
insert_edge( graph, node_src, arr_v[j-1], arr_w[j-1]);
j--;
}
}
}
else /* fopen() returned NULL */
{
perror(filename);
}
fclose(file_pointer);
/*Display the Graph Adj list*/
printf("\n******************************\n\tGraph Adj List \n******************************");
display_adj_list(graph);
printf("\n\n");
/************************************************
****CODE FOR Dijkstra_algorithm****
*************************************************/
dist = (int *)malloc(node_count * sizeof(int));
previous = (int *)malloc(node_count * sizeof(int));
flag = (int *)malloc(node_count * sizeof(int));
for (i=0; i<node_count; ++i)
{
dist[i] = INFINITY;
previous[i] = UNDEFINED;
flag[i] = 0;
}
while(1)
{
printf("Enter the Source Node in the Graph: ");
scanf("%d", &source);
if(source <= node_count && source > 0 )
break;
printf("Error : Source Node does not exist in the Graph.\n\n");
}
dist[source-1] = 0;
previous[source-1] = -1;
for( i=0; i<node_count; ++i)
{
insert_into_pqueue( &start, &end, &prev, &comp, i+1, dist[i] );
heapify_down(&comp);
}
printf("\nPriority Queue After Initializations.\n");
printf("*************************************\n");
display_priority_queue(start);
while(1)
{
value_u = dequeue_from_pqueue(&start, &end, &prev, &comp);
heapify_up(&start, &comp);
if (value_u == -1)
{ break; }
value_u--;
flag[value_u] = 1;
struct adj_list_edge* temp;
temp = graph->array[value_u].head;
while(temp)
{
value_v = temp->vertex;
value_v--;
if( flag[value_v] == 0)
{
alt = dist[value_u] + temp->weight;
if( alt < dist[value_v] )
{
dist[value_v] = alt;
previous[value_v] = value_u+1;
value_v++;
decrease_priority(&start, &comp, value_v, alt );
heapify_down(&comp);
}
}
temp = temp->next;
}
}
/*Displaying the final results*/
printf("\nSource Destination Cost Path\n");
for(i=0; i<node_count; ++i)
{
printf(" %d ", source);
printf(" %d ", i+1);
if(dist[i]<INFINITY)
{ printf(" %d ", dist[i]); }
else
{ printf(" INFINITY "); }
if((i+1)==source)
{ printf("[ %d ]\n",source); }
else if(dist[i]==INFINITY)
{ printf("\n"); }
else
{ k=0;
j=i;
arr_v[k]=j+1;
k++;
while((j+1) != source)
{
arr_v[k]=previous[j];
j = previous[j]-1;
k++;
}
printf("[ %d", arr_v[k-1]);
for(j=k-1; j>0; j--)
{
printf("->%d", arr_v[j-1]);
}
printf(" ]\n");
}
}
return 0;
}
/*End of the main program*/
/*************************/
/*Function defination to create a graph with ajd lists*/
struct graph* create_graph(int vertex)
{
struct graph* g = (struct graph*) malloc(sizeof(struct graph));
g->no_vertex = vertex;
/*Allocate memory for the adj lists*/
g->array = (struct adj_list*) malloc(vertex * sizeof(struct adj_list));
/*Init the head of each ajd list head with NULL*/
while(vertex>0)
{
g->array[vertex-1].head = NULL;
vertex--;
}
return g;
}
/*Insert edge node in to a given adj list in the graph structure*/
void insert_edge(struct graph* graph, int node, int vertex, int weight)
{
struct adj_list_edge* new_edge = (struct adj_list_edge*) malloc(sizeof(struct adj_list_edge));
new_edge->vertex = vertex;
new_edge->weight = weight;
new_edge->next = NULL;
new_edge->next = graph->array[node].head;
graph->array[node].head = new_edge;
}
/*Function Defination for displaying the Graph adj list */
void display_adj_list(struct graph* graph)
{
int i;
for (i=0; i<graph->no_vertex; ++i)
{
struct adj_list_edge* temp;
temp = graph->array[i].head;
printf("\n Adjacency list of vertex %d\n head ", i+1);
while(temp)
{
printf("-> %d/%d", temp->vertex, temp->weight);
temp = temp->next;
}
printf("\n");
}
}
/*Function defination to insert the node into the heap*/
void insert_into_pqueue(heap_node** start, heap_node** end, heap_node** prev, heap_node** comp, int vertex, int weight)
{
heap_node* temp_node = NULL;
temp_node = (heap_node*) malloc(sizeof(heap_node));
if (temp_node == NULL)
{
printf("Memory for Heap Node can't be allocated");
exit(0);
}
temp_node->vertex = vertex;
temp_node->vertex_weight = weight;
/*If there is no elements in the Heap */
if(*end == NULL)
{
*start = temp_node;
*end = temp_node;
*prev = temp_node;
*comp = temp_node;
/*Init the pointers with NULL Values*/
temp_node->parent = NULL;
temp_node->left_child = NULL;
temp_node->right_child = NULL;
temp_node->next_node = NULL;
temp_node->prev_node = NULL;
}
else /*If the Heap is already having nodes it it*/
{
if((*end)->left_child == NULL)
{
(*end)->left_child = temp_node;
/*Manupulating the pointers values*/
temp_node->parent = *end;
temp_node->left_child = NULL;
temp_node->right_child = NULL;
temp_node->next_node = NULL;
temp_node->prev_node = *prev;
(*prev)->next_node = temp_node;
*prev = temp_node;
*comp = temp_node;
}
else
{
(*end)->right_child = temp_node;
/*Manupulating the pointers values*/
temp_node->parent = *end;
temp_node->left_child = NULL;
temp_node->right_child = NULL;
temp_node->next_node = NULL;
temp_node->prev_node = *prev;
(*prev)->next_node = temp_node;
*prev = temp_node;
*comp = temp_node;
*end = (*end)->next_node;
}
}
}
/*Function defination of delete from Priority Queue*/
int dequeue_from_pqueue(heap_node** start, heap_node** end, heap_node** prev, heap_node** comp)
{
int element = -1;
if(*start == NULL)
{
return element;
}
element = (*start)->vertex;
if((*start)->left_child == NULL)
{
free(*start);
*start = NULL;
*end = NULL;
*prev = NULL;
*comp = NULL;
}
else
{
if((*end)->left_child == NULL)
{
(*start)->vertex_weight = (*prev)->vertex_weight;
(*start)->vertex = (*prev)->vertex;
*end = (*end)->prev_node;
(*end)->right_child = NULL;
*comp = *prev;
*prev = (*prev)->prev_node;
(*prev)->next_node = NULL;
free(*comp);
*comp = *prev;
}
else
{
(*start)->vertex_weight = (*prev)->vertex_weight;
(*start)->vertex = (*prev)->vertex;
(*end)->left_child = NULL;
*comp = *prev;
*prev = (*prev)->prev_node;
(*prev)->next_node = NULL;
free(*comp);
*comp = *prev;
}
}
return element;
}
/*Function defination to decrease priority of a node in the Priority Queue*/
void decrease_priority(heap_node** start, heap_node** comp, int value_v, int alt)
{
int i;
*comp = *start;
while(1)
{
if(*comp == NULL) break;
if((*comp)->vertex == value_v)
{
(*comp)->vertex_weight = alt;
return;
}
*comp = (*comp)->next_node;
}
}
/*Function defination to diplay the Priority Queue*/
void display_priority_queue(heap_node* start)
{
if(start == NULL)
{
printf("Queue is empty...\n\n");
return;
}
heap_node* temp_start = start;
while(1)
{
if(temp_start == NULL)break;
printf("%d", temp_start->vertex,temp_start->vertex_weight);
if(temp_start->vertex_weight == INFINITY)
printf("/INFY ");
else
printf("/%d ", temp_start->vertex_weight);
temp_start = temp_start->next_node;
}
printf("\n\n");
}
/*Function defination to heapify the heap from down*/
void heapify_down(heap_node** comp)
{
int i, j;
while((*comp)->parent != NULL)
{
heap_node* temp_parent = (*comp)->parent;
if( (*comp)->vertex_weight < temp_parent->vertex_weight )
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_parent->vertex_weight;
(*comp)->vertex = temp_parent->vertex;
*comp = (*comp)->parent;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
}
else
{ break; }
}
}
/*Function defination to heapify the heap from down*/
void heapify_up(heap_node** start, heap_node** comp)
{
int i, j;
*comp = *start;
/*If No node is there in Heap*/
if(*start == NULL)
{ return; }
/*If just in one node is there in the Heap*/
if((*comp)->left_child == NULL && (*comp)->right_child == NULL)
{ return; }
/*If only two nodes are there in the Heap*/
if((*comp)->right_child == NULL)
{
heap_node* temp_child = (*comp)->left_child;
if((*comp)->vertex_weight > temp_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_child->vertex_weight;
(*comp)->vertex = temp_child->vertex;
*comp = (*comp)->left_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
}
return;
}
/*If more than two nodes are there in the Heap*/
while((*comp)->left_child != NULL || (*comp)->right_child != NULL )
{
if((*comp)->right_child == NULL)
{
heap_node* temp_left_child = (*comp)->left_child;
if((*comp)->vertex_weight >= temp_left_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_left_child->vertex_weight;
(*comp)->vertex = temp_left_child->vertex;
*comp = (*comp)->left_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
}
return;
}
else
{
heap_node* temp_left_child = (*comp)->left_child;
heap_node* temp_right_child = (*comp)->right_child;
if(temp_left_child->vertex_weight == temp_right_child->vertex_weight)
{
if((*comp)->vertex_weight <= temp_left_child->vertex_weight)
{
return;
}
if((*comp)->vertex_weight > temp_left_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_left_child->vertex_weight;
(*comp)->vertex = temp_left_child->vertex;
*comp = (*comp)->left_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
continue;
}
}
else if(temp_left_child->vertex_weight < temp_right_child->vertex_weight)
{
if((*comp)->vertex_weight <= temp_left_child->vertex_weight)
{
return;
}
else if((*comp)->vertex_weight > temp_left_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_left_child->vertex_weight;
(*comp)->vertex = temp_left_child->vertex;
*comp = (*comp)->left_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
continue;
}
}
else
{
if((*comp)->vertex_weight <= temp_right_child->vertex_weight)
{
return;
}
if((*comp)->vertex_weight > temp_right_child->vertex_weight)
{
i = (*comp)->vertex_weight;
j = (*comp)->vertex;
(*comp)->vertex_weight = temp_right_child->vertex_weight;
(*comp)->vertex = temp_right_child->vertex;
*comp = (*comp)->right_child;
(*comp)->vertex_weight = i;
(*comp)->vertex = j;
continue;
}
}
}
}
}
/*******************************
END OF THE PROGRAM
********************************/
No comments:
Post a Comment