Given a binary tree T=(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 tree T.
Sample Input File can be found here.
Program Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*Declaration of node structer for link list*/
typedef struct t_node{
int weight;
int opt_value;
int ind_set_size;
struct t_node *left_node, *right_node;
}tree_node;
/*Declaration of functions*/
int build_binary_tree(tree_node** root, int *tree_nodes);
int add_new_node(tree_node** node, int *tree_nodes, int current_loc);
void display_binary_tree(tree_node *root);
void display_node(tree_node *node);
void compute_optimal_value(tree_node** node);
void display_tree_independent_set(tree_node** node);
/*Starting of the Main Function*/
int main()
{
int temp, node_count, buffer_entry;
const char filename[] = "tree_nodes.csv";
char buffer[BUFSIZ], buffer_values[BUFSIZ], *ptr;
int *tree_nodes;
/*Declaring the root pointer of the tree*/
tree_node *root;
/*File Pointers to read the chain nodes weight file.*/
FILE *file_pointer;
/*Initlizing the buffer with zeros (0) for post processing.*/
for(temp =0; temp<BUFSIZ; temp++)
{
buffer[temp] = -1;
}
/* Reading the content from the CSV file, Count number of nodes in the tree and storing the pre-order in the buffer for post insertation into link list.*/
file_pointer = fopen(filename, "r");
if ( file_pointer )
{
fgets(buffer, sizeof buffer, file_pointer);
buffer_entry = 0;
temp = 0;
if(strlen(buffer)>0)
{
strcpy(buffer_values, buffer);
ptr = (char *)strtok(buffer, "->");
while(ptr!=NULL)
{
buffer[temp] = atoi(ptr);
if( buffer[temp]>=0 )
{
buffer_entry = buffer_entry + 1;
}
else
{
printf("Please Enter non-zero and non-negative values for the node weight\n\n");
exit(0);
}
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);
/*Allocating the tree_nodes Array's Dynamically.. */
tree_nodes = (int *)malloc(buffer_entry * sizeof(int));
/*Reading the entries and storing them in newly allocated array for binary tree creatation*/
temp = 0;
ptr = (char *)strtok(buffer_values, "->");
while(ptr!=NULL)
{
tree_nodes[temp] = atoi(ptr);
if( tree_nodes[temp]>0 )
{
node_count = node_count + 1;
}
temp++;
ptr = (char *)strtok(NULL,"->");
}
if(node_count ==0)
{
printf("Tree is empty....\n");
exit(0);
}
printf("\nNumber of Nodes in the tree is: %d\n\n", node_count);
/*Buils\ding the binary tree from the entries*/
build_binary_tree(&root, tree_nodes);
/*Computing the node Optimal Values*/
compute_optimal_value(&root);
/*Displaying pre-order of the Binary Tree*/
printf("Binary Tree After computing the optimal values:\n");
display_binary_tree(root);
/*Displaying the Independent Set and its size for the Binary Tree.*/
printf("\n\nThe maximum independent set value is: %d", root->opt_value);
printf("\n\nThe size of the Independent Set is: %d", root->ind_set_size);
printf("\n\nElements in the Independent Set are:\n");
display_tree_independent_set(&root);
printf("\n**********************************************\n");
}
/*************************************************************
*************************************************************/
/*Function Defination to build Binary Tree*/
int build_binary_tree(tree_node** root, int *tree_nodes)
{
int current_loc = 0;
if(tree_nodes[current_loc] > 0)
{
tree_node* temp = NULL;
if( (temp = (tree_node *) malloc(sizeof(tree_node))) ==NULL)
{
printf("\nMEMORY ALLOCATION UNSUCCESSFUL");
exit(1);
}
temp->weight = tree_nodes[current_loc];
temp->opt_value = 0;
temp->ind_set_size = 0;
temp->left_node = NULL;
temp->right_node = NULL;
*root = temp;
current_loc = current_loc + 1;
/*Recursively building the left sub tree*/
current_loc = add_new_node(&(temp->left_node), tree_nodes, current_loc);
/*Recursively building the right sub tree*/
current_loc = add_new_node(&(temp->right_node), tree_nodes, current_loc);
}
else
{
printf("Please Enter non-zero and non-negative values for the root node\n\n");
exit(0);
}
}
/*Function Defination to add new node into binary tree*/
int add_new_node(tree_node** node, int *tree_nodes, int current_loc)
{
if(tree_nodes[current_loc] > 0)
{
tree_node *temp;
if( (temp = (tree_node *) malloc(sizeof(tree_node))) ==NULL)
{
printf("\nMEMORY ALLOCATION UNSUCCESSFUL");
exit(1);
}
temp->weight = tree_nodes[current_loc];
temp->opt_value = 0;
temp->ind_set_size = 0;
temp->left_node = NULL;
temp->right_node = NULL;
*node = temp;
current_loc = current_loc + 1;
/*Recursively building the left sub tree*/
current_loc = add_new_node(&(temp->left_node), tree_nodes, current_loc);
/*Recursively building the right sub tree*/
current_loc = add_new_node(&(temp->right_node), tree_nodes, current_loc);
}
else
{
current_loc = current_loc + 1;
return current_loc;
}
}
/*Function Defination to display the Binary Tree*/
void display_binary_tree(tree_node *root)
{
tree_node* temp = root;
if(temp == NULL)
{
printf("Binary Tree is empty!\n");return;
}
else
{
printf("%d/%d ", temp->weight, temp->opt_value);
display_node(temp->left_node);
display_node(temp->right_node);
}
}
void display_node(tree_node *node)
{
tree_node* temp = node;
if(temp != NULL)
{
printf("%d/%d ", temp->weight, temp->opt_value);
display_node(temp->left_node);
display_node(temp->right_node);
}
return;
}
/*Function Defination to compute the node optimal values of the Binary Tree*/
void compute_optimal_value(tree_node** node)
{
int grand_child_optimal = 0;
int child_optimal = 0;
int grand_child_set_size = 0;
int child_set_size = 0;
tree_node* temp = *node;
tree_node* temp_left = (*node)->left_node;
tree_node* temp_right = (*node)->right_node;
if(temp_left != NULL)
compute_optimal_value(&(temp->left_node));
if(temp_right != NULL)
compute_optimal_value(&(temp->right_node));
/*Calculating the optimal value of Leaf Node*/
if( (temp_left == NULL) && (temp_right == NULL))
{
temp->opt_value = temp->weight;
temp->ind_set_size = 1;
return;
}
/*Calculating the optinal value of the Non-leaf Node with two children*/
if( (temp_left != NULL) && (temp_right != NULL))
{
if( temp_left->left_node != NULL )
{
grand_child_optimal = grand_child_optimal + (temp_left->left_node)->opt_value;
grand_child_set_size = grand_child_set_size + (temp_left->left_node)->ind_set_size;
}
if( temp_left->right_node != NULL )
{
grand_child_optimal = grand_child_optimal + (temp_left->right_node)->opt_value;
grand_child_set_size = grand_child_set_size + (temp_left->right_node)->ind_set_size;
}
if( temp_right->left_node != NULL )
{
grand_child_optimal = grand_child_optimal + (temp_right->left_node)->opt_value;
grand_child_set_size = grand_child_set_size + (temp_right->left_node)->ind_set_size;
}
if( temp_right->right_node != NULL )
{
grand_child_optimal = grand_child_optimal + (temp_right->right_node)->opt_value;
grand_child_set_size = grand_child_set_size + (temp_right->right_node)->ind_set_size;
}
child_optimal = temp_left->opt_value + temp_right->opt_value;
child_set_size = temp_left->ind_set_size + temp_right->ind_set_size;
if( (temp->weight + grand_child_optimal) > child_optimal)
{
temp->opt_value = (temp->weight) + grand_child_optimal;
temp->ind_set_size = 1 + grand_child_set_size;
}
else
{
temp->opt_value = child_optimal;
temp->ind_set_size = child_set_size;
}
return;
}
/*Calculating the optinal value of the Left Node is NULL*/
if( temp_left == NULL )
{
if( temp_right->left_node != NULL )
{
grand_child_optimal = grand_child_optimal + (temp_right->left_node)->opt_value;
grand_child_set_size = grand_child_set_size + (temp_right->left_node)->ind_set_size;
}
if( temp_right->right_node != NULL )
{
grand_child_optimal = grand_child_optimal + (temp_right->right_node)->opt_value;
grand_child_set_size = grand_child_set_size + (temp_right->right_node)->ind_set_size;
}
child_optimal = temp_right->opt_value;
child_set_size = temp_right->ind_set_size;
if( (temp->weight + grand_child_optimal) > child_optimal)
{
temp->opt_value = (temp->weight) + grand_child_optimal;
temp->ind_set_size = 1 + grand_child_set_size;
}
else
{
temp->opt_value = child_optimal;
temp->ind_set_size = child_set_size;
}
return;
}
/*Calculating the optinal value of the Right Node is NULL*/
if( temp_right == NULL)
{
if( temp_left->left_node != NULL )
{
grand_child_optimal = grand_child_optimal + (temp_left->left_node)->opt_value;
grand_child_set_size = grand_child_set_size + (temp_left->left_node)->ind_set_size;
}
if( temp_left->right_node != NULL )
{
grand_child_optimal = grand_child_optimal + (temp_left->right_node)->opt_value;
grand_child_set_size = grand_child_set_size + (temp_left->right_node)->ind_set_size;
}
child_optimal = temp_left->opt_value;
child_set_size = temp_left->ind_set_size;
if( (temp->weight + grand_child_optimal) > child_optimal)
{
temp->opt_value = (temp->weight) + grand_child_optimal;
temp->ind_set_size = 1 + grand_child_set_size;
}
else
{
temp->opt_value = child_optimal;
temp->ind_set_size = child_set_size;
}
return;
}
}
/*Function Defination to Display the Independent Set and its size for the Binary Tree.*/
void display_tree_independent_set(tree_node** node)
{
tree_node* temp = *node;
tree_node* temp_left = (*node)->left_node;
tree_node* temp_right = (*node)->right_node;
/*Node is a Leaf Node*/
if( (temp_left == NULL) && (temp_right == NULL))
{
printf("%d ", temp->weight);
return;
}
/*Node having both left and right sub-tree*/
if( (temp_left != NULL) && (temp_right != NULL))
{
if( temp->opt_value > (temp_left->opt_value + temp_right->opt_value))
{
printf("%d ", temp->weight);
if( temp_left->left_node != NULL )
{
display_tree_independent_set( &(temp_left->left_node));
}
if( temp_left->right_node != NULL )
{
display_tree_independent_set( &(temp_left->right_node));
}
if( temp_right->left_node != NULL )
{
display_tree_independent_set( &(temp_right->left_node));
}
if( temp_right->right_node != NULL )
{
display_tree_independent_set( &(temp_right->right_node));
}
}
else
{
display_tree_independent_set( &temp_left );
display_tree_independent_set( &temp_right );
}
return;
}
/*Node having Right sub-tree only*/
if( temp_left == NULL )
{
if( temp->opt_value > temp_right->opt_value )
{
printf("%d ", temp->weight);
if( temp_right->left_node != NULL )
{
display_tree_independent_set( &(temp_right->left_node));
}
if( temp_right->right_node != NULL )
{
display_tree_independent_set( &(temp_right->right_node));
}
}
else
{
display_tree_independent_set( &temp_right );
}
return;
}
/*Node having Left sub-tree only*/
if( temp_right == NULL )
{
if( temp->opt_value > temp_left->opt_value )
{
printf("%d ", temp->weight);
if( temp_left->left_node != NULL )
{
display_tree_independent_set( &(temp_left->left_node));
}
if( temp_left->right_node != NULL )
{
display_tree_independent_set( &(temp_left->right_node));
}
}
else
{
display_tree_independent_set( &temp_left );
}
return;
}
} /*End of Function*/
/*******End of Program********/
No comments:
Post a Comment