Que) Given a chain G=(V,E) where each node i has a weight W_i. A maximum independent set is an independent set having maximum cumulative node weight. Write a program to find maximum independent set in the given chain graph G.
Input file formats can be found here.
Program Code
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*Starting of the Main Function*/
int main()
{
int temp, node_count;
const char filename[] = "chain_nodes.csv";
char buffer[BUFSIZ], buffer_values[BUFSIZ], *ptr;
/*Pointers to necessary Arrays*/
int *node_weights;
int *opt_value_of_node;
int *index_of_last_opt_node;
/*File Pointers to read the chain nodes weight file.*/
FILE *file_pointer;
/* Count number of entries in CVS file.*/
file_pointer = fopen(filename, "r");
if ( file_pointer )
{
fgets(buffer, sizeof buffer, file_pointer);
node_count = 0;
if(strlen(buffer)>0)
{
strcpy(buffer_values, buffer);
ptr = (char *)strtok(buffer, "->");
node_count = node_count + 1;
ptr = (char *)strtok(NULL,"->");
while(ptr!=NULL)
{
node_count = node_count + 1;
ptr = (char *)strtok(NULL,"->");
}
}
else
{
printf("File is Empty. please enter the node weights of the chain into the file\n\n");
exit(0);
}
}
else /* fopen() returned NULL */
{
perror(filename);
}
fclose(file_pointer);
printf("\n\nNumber of Nodes in the Chain: %d\n\n", node_count);
/*Allocating the necessary Array's Dynamically.. */
node_weights = (int *)malloc(node_count * sizeof(int));
opt_value_of_node = (int *)malloc(node_count * sizeof(int));
index_of_last_opt_node = (int *)malloc(node_count * sizeof(int));
temp=0;
ptr = (char *)strtok(buffer_values, "->");
node_weights[temp] = atoi(ptr);
if(node_weights[temp] < 1)
{
printf("Please Enter non-zero and non-negative values for the node weight\n\n");
exit(0);
}
temp++;
ptr = (char *)strtok(NULL,"->");
while(ptr!=NULL)
{
node_weights[temp] = atoi(ptr);
if(node_weights[temp] < 1)
{
printf("Please Enter non-zero and non-negative values for the node weight\n\n");
exit(0);
}
temp++;
ptr = (char *)strtok(NULL,"->");
}
for(temp = 0; temp<node_count; temp++)
{
printf("%d ",node_weights[temp]);
}
printf("\n\n");
for(temp = 0; temp<node_count; temp++)
{
if(temp == 0)
{
opt_value_of_node[temp] = node_weights[temp];
index_of_last_opt_node[temp] = temp;
}
else if(temp == 1)
{
if(opt_value_of_node[temp-1] >= node_weights[temp] )
{
opt_value_of_node[temp] = opt_value_of_node[temp-1];
index_of_last_opt_node[temp] = temp-1;
}
else
{
opt_value_of_node[temp] = node_weights[temp];
index_of_last_opt_node[temp] = temp;
}
}
else if(temp == 2)
{
if(opt_value_of_node[temp-1] >= (node_weights[temp]+opt_value_of_node[temp-2]))
{
opt_value_of_node[temp] = opt_value_of_node[temp-1];
index_of_last_opt_node[temp] = temp-1;
}
else
{
opt_value_of_node[temp] = node_weights[temp]+opt_value_of_node[temp-2];
index_of_last_opt_node[temp] = temp-2;
}
}
else
{
if(opt_value_of_node[temp-1] >= (node_weights[temp]+opt_value_of_node[temp-2]))
{
opt_value_of_node[temp] = opt_value_of_node[temp-1];
index_of_last_opt_node[temp] = temp-1;
}
else
{
opt_value_of_node[temp] = node_weights[temp]+opt_value_of_node[temp-2];
if(opt_value_of_node[temp-2]> opt_value_of_node[temp-3])
{
index_of_last_opt_node[temp] = temp-2;
}
else
{
index_of_last_opt_node[temp] = temp-3;
}
}
}
}
/*Printing the maximum independent set value and nodes weights*/
temp = node_count -1;
if(opt_value_of_node[temp-1] >= opt_value_of_node[temp])
{
printf("The maximum independent set value is : %d \n\n", opt_value_of_node[temp-1] );
temp = temp -1;
printf("The maximum independent set is:\n %d ", node_weights[temp]);
while(temp != index_of_last_opt_node[temp])
{
temp = index_of_last_opt_node[temp];
printf("%d ", node_weights[temp]);
}
}
else
{
printf("The maximum independent set value is : %d \n\n", opt_value_of_node[temp] );
printf("The maximum independent set is:\n %d ", node_weights[temp]);
while(temp != index_of_last_opt_node[temp])
{
temp = index_of_last_opt_node[temp];
printf("%d ", node_weights[temp]);
}
}
printf("\n\n");
}
/***********************
END OF THE PROGRAM
************************/
Input file formats can be found here.
Program Code
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*Starting of the Main Function*/
int main()
{
int temp, node_count;
const char filename[] = "chain_nodes.csv";
char buffer[BUFSIZ], buffer_values[BUFSIZ], *ptr;
/*Pointers to necessary Arrays*/
int *node_weights;
int *opt_value_of_node;
int *index_of_last_opt_node;
/*File Pointers to read the chain nodes weight file.*/
FILE *file_pointer;
/* Count number of entries in CVS file.*/
file_pointer = fopen(filename, "r");
if ( file_pointer )
{
fgets(buffer, sizeof buffer, file_pointer);
node_count = 0;
if(strlen(buffer)>0)
{
strcpy(buffer_values, buffer);
ptr = (char *)strtok(buffer, "->");
node_count = node_count + 1;
ptr = (char *)strtok(NULL,"->");
while(ptr!=NULL)
{
node_count = node_count + 1;
ptr = (char *)strtok(NULL,"->");
}
}
else
{
printf("File is Empty. please enter the node weights of the chain into the file\n\n");
exit(0);
}
}
else /* fopen() returned NULL */
{
perror(filename);
}
fclose(file_pointer);
printf("\n\nNumber of Nodes in the Chain: %d\n\n", node_count);
/*Allocating the necessary Array's Dynamically.. */
node_weights = (int *)malloc(node_count * sizeof(int));
opt_value_of_node = (int *)malloc(node_count * sizeof(int));
index_of_last_opt_node = (int *)malloc(node_count * sizeof(int));
temp=0;
ptr = (char *)strtok(buffer_values, "->");
node_weights[temp] = atoi(ptr);
if(node_weights[temp] < 1)
{
printf("Please Enter non-zero and non-negative values for the node weight\n\n");
exit(0);
}
temp++;
ptr = (char *)strtok(NULL,"->");
while(ptr!=NULL)
{
node_weights[temp] = atoi(ptr);
if(node_weights[temp] < 1)
{
printf("Please Enter non-zero and non-negative values for the node weight\n\n");
exit(0);
}
temp++;
ptr = (char *)strtok(NULL,"->");
}
for(temp = 0; temp<node_count; temp++)
{
printf("%d ",node_weights[temp]);
}
printf("\n\n");
for(temp = 0; temp<node_count; temp++)
{
if(temp == 0)
{
opt_value_of_node[temp] = node_weights[temp];
index_of_last_opt_node[temp] = temp;
}
else if(temp == 1)
{
if(opt_value_of_node[temp-1] >= node_weights[temp] )
{
opt_value_of_node[temp] = opt_value_of_node[temp-1];
index_of_last_opt_node[temp] = temp-1;
}
else
{
opt_value_of_node[temp] = node_weights[temp];
index_of_last_opt_node[temp] = temp;
}
}
else if(temp == 2)
{
if(opt_value_of_node[temp-1] >= (node_weights[temp]+opt_value_of_node[temp-2]))
{
opt_value_of_node[temp] = opt_value_of_node[temp-1];
index_of_last_opt_node[temp] = temp-1;
}
else
{
opt_value_of_node[temp] = node_weights[temp]+opt_value_of_node[temp-2];
index_of_last_opt_node[temp] = temp-2;
}
}
else
{
if(opt_value_of_node[temp-1] >= (node_weights[temp]+opt_value_of_node[temp-2]))
{
opt_value_of_node[temp] = opt_value_of_node[temp-1];
index_of_last_opt_node[temp] = temp-1;
}
else
{
opt_value_of_node[temp] = node_weights[temp]+opt_value_of_node[temp-2];
if(opt_value_of_node[temp-2]> opt_value_of_node[temp-3])
{
index_of_last_opt_node[temp] = temp-2;
}
else
{
index_of_last_opt_node[temp] = temp-3;
}
}
}
}
/*Printing the maximum independent set value and nodes weights*/
temp = node_count -1;
if(opt_value_of_node[temp-1] >= opt_value_of_node[temp])
{
printf("The maximum independent set value is : %d \n\n", opt_value_of_node[temp-1] );
temp = temp -1;
printf("The maximum independent set is:\n %d ", node_weights[temp]);
while(temp != index_of_last_opt_node[temp])
{
temp = index_of_last_opt_node[temp];
printf("%d ", node_weights[temp]);
}
}
else
{
printf("The maximum independent set value is : %d \n\n", opt_value_of_node[temp] );
printf("The maximum independent set is:\n %d ", node_weights[temp]);
while(temp != index_of_last_opt_node[temp])
{
temp = index_of_last_opt_node[temp];
printf("%d ", node_weights[temp]);
}
}
printf("\n\n");
}
/***********************
END OF THE PROGRAM
************************/
No comments:
Post a Comment