Pages

Write a program to find maximum independent set in the given chain graph G

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
************************/

No comments:

Post a Comment