My first solution of the 18 points exam 20160222

20160222.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//DA RIFARE PALESEMENTE CON L'ADJACENCY MATRIX

enum color{RED,BLACK};
enum yesno{YES,NO};

typedef struct edge_t edge_t;
typedef struct edge_list_item_t edge_list_item_t;
typedef struct vertex_t vertex_t;
typedef struct vertex_list_item_t vertex_list_item_t;

struct edge_t{
    vertex_t *V[2];
    int val;
};

struct edge_list_item_t{
    edge_t *this;
    edge_list_item_t *next;
};

struct vertex_t{
    char *id;
    enum color col;
    enum yesno visited;
    edge_list_item_t *edge_list;
};

struct vertex_list_item_t{
    vertex_t *this;
    vertex_list_item_t *next;
};

void specialPath(vertex_list_item_t *v_list);
void findPath_r(vertex_t *v, int weightSum, int *bestWeight, vertex_list_item_t **pathStack, vertex_list_item_t **bestPath);
void printVList(vertex_list_item_t *path);
void readAndStore(FILE *input, vertex_list_item_t **v_list, edge_list_item_t **e_list);
vertex_t *findOrInsertVertex(vertex_list_item_t **v_list, char *id, char *col);
int insertEdge(edge_list_item_t **e_list, edge_t *new_edge);
void freeListOnly(vertex_list_item_t *v);
void specialSubset(vertex_list_item_t *v_list, edge_list_item_t *e_list);
void findSubset(vertex_list_item_t *v_from, edge_list_item_t *e_list, vertex_list_item_t *v_removed,
                vertex_list_item_t *v_taken, vertex_list_item_t **v_best, int *best_w, int balance);

int main(int argc, char **argv) {
    FILE *input;
    vertex_list_item_t *v_list=NULL;
    edge_list_item_t *e_list=NULL;

    if(argc!=2){
        printf("ERROR: wrong number of arguments.\n");
        exit(EXIT_FAILURE);
    }

    input=fopen(argv[1],"r");
    if(input==NULL){
        printf("ERROR: can't open file\n");
        exit(EXIT_FAILURE);
    }

    readAndStore(input,&v_list,&e_list);

    fclose(input);

    specialPath(v_list);
    printf("---\n");
    specialSubset(v_list,e_list);

    //free everything

    return 0;
}

void readAndStore(FILE *input, vertex_list_item_t **v_list, edge_list_item_t **e_list){
    vertex_t *vert1, *vert2;
    edge_t *new_edge;
    char idV1[21], idV2[21], colV1[6], colV2[6];
    int val;
    if(idV1==NULL||idV2==NULL)exit(EXIT_FAILURE);
    while(fscanf(input,"%s %s %d %s %s",idV1,colV1,&val,idV2,colV2)==5){
        vert1=findOrInsertVertex(v_list, idV1, colV1);
        vert2=findOrInsertVertex(v_list, idV2, colV2);
        new_edge=(edge_t*)malloc(sizeof(edge_t));
        if(new_edge==NULL)exit(EXIT_FAILURE);
        new_edge->V[0]=vert1;
        new_edge->V[1]=vert2;
        new_edge->val=val;
        insertEdge(&vert1->edge_list,new_edge);
        insertEdge(&vert2->edge_list,new_edge);
        insertEdge(e_list,new_edge);
    }
}

vertex_t *findOrInsertVertex(vertex_list_item_t **v_list, char *id, char *col){
    vertex_t *vert;
    vertex_list_item_t *vert_list_item;
    for(vert_list_item=*v_list;vert_list_item!=NULL&&strcmp(vert_list_item->this->id,id)!=0;vert_list_item=vert_list_item->next);
    if(vert_list_item==NULL){
        vert=(vertex_t*)malloc(sizeof(vertex_t));
        vert_list_item=(vertex_list_item_t*)malloc(sizeof(vertex_list_item_t));
        if(vert==NULL||vert_list_item==NULL)exit(EXIT_FAILURE);
        vert->col=strcmp(col,"RED")==0?RED:BLACK;
        vert->visited=NO;
        vert->edge_list=NULL;
        vert->id=strdup(id);
        if(vert->id==NULL)exit(EXIT_FAILURE);
        vert_list_item->this=vert;
        vert_list_item->next=*v_list;
        *v_list=vert_list_item;
    }
    else vert=vert_list_item->this;
    return vert;
}

int insertEdge(edge_list_item_t **e_list, edge_t *new_edge){
    edge_list_item_t *new_e_item;
    new_e_item=(edge_list_item_t*)malloc(sizeof(edge_list_item_t));
    if(new_e_item==NULL)exit(EXIT_FAILURE);
    new_e_item->this=new_edge;
    new_e_item->next=*e_list;
    *e_list=new_e_item;
    return 1;
}

void specialPath(vertex_list_item_t *v_list){
    vertex_list_item_t *pathStack=NULL, *bestPath=NULL, *current_v;
    int bestWeight=0;

    for(current_v=v_list;current_v!=NULL;current_v=current_v->next)
        findPath_r(current_v->this,0,&bestWeight,&pathStack,&bestPath);

    printVList(bestPath);
}

void findPath_r(vertex_t *v, int weightSum, int *bestWeight, vertex_list_item_t **pathStack, vertex_list_item_t **bestPath){
    edge_list_item_t *current_e;
    vertex_list_item_t *tmpp,*tmpb;
    int i;

    if(v->visited==YES||(*pathStack!=NULL&&(*pathStack)->this->col==RED&&v->col==RED))return;
    v->visited=YES;
    tmpp=(vertex_list_item_t*)malloc(sizeof(vertex_list_item_t));//Add to path
    tmpp->this=v;
    tmpp->next=*pathStack;
    *pathStack=tmpp;

    for(current_e=v->edge_list;current_e!=NULL;current_e=current_e->next)
        for(i=0;i<2;i++)findPath_r(current_e->this->V[i],weightSum+current_e->this->val,bestWeight,pathStack,bestPath);

    if(weightSum>=*bestWeight){
        *bestWeight=weightSum;
        freeListOnly(*bestPath);
        *bestPath=NULL;
        for(tmpp=*pathStack;tmpp!=NULL;tmpp=tmpp->next){
            tmpb=(vertex_list_item_t*)malloc(sizeof(vertex_list_item_t));
            tmpb->this=tmpp->this;
            tmpb->next=*bestPath;
            *bestPath=tmpb;
        }
    }

    *pathStack=(*pathStack)->next;//Remove from path
    free(tmpp);
    v->visited=NO;
}

void printVList(vertex_list_item_t *path){
    if(path==NULL)return;
    printf("%s\n",path->this->id);
    printVList(path->next);
}

void specialSubset(vertex_list_item_t *v_list, edge_list_item_t *e_list){
    vertex_list_item_t *v_best=NULL;
    int best_w=0;
    findSubset(v_list,e_list,NULL,NULL,&v_best,&best_w,0);
    printVList(v_best);
}

void findSubset(vertex_list_item_t *v_from, edge_list_item_t *e_list, vertex_list_item_t *v_removed,
                vertex_list_item_t *v_taken, vertex_list_item_t **v_best, int *best_w, int balance){
    vertex_list_item_t *tmp,*tmpb;
    edge_list_item_t *c_e;
    int w_sum;

    if(v_from==NULL){
        if(balance<3&&balance>-3){
            w_sum=0;
            for(c_e=e_list;c_e!=NULL;c_e=c_e->next){
                for(tmp=v_removed;tmp!=NULL&&c_e->this->V[0]!=v_removed->this&&c_e->this->V[1]!=v_removed->this;tmp=tmp->next);
                if(tmp==NULL)w_sum+=c_e->this->val;
            }

            if(w_sum>*best_w){
                *best_w=w_sum;
                freeListOnly(*v_best);
                *v_best=NULL;
                for(tmp=v_taken;tmp!=NULL;tmp=tmp->next){
                    tmpb=(vertex_list_item_t*)malloc(sizeof(vertex_list_item_t));
                    tmpb->this=tmp->this;
                    tmpb->next=*v_best;
                    *v_best=tmpb;
                }
            }
        }
        return;
    }

    tmp=(vertex_list_item_t*)malloc(sizeof(vertex_list_item_t));
    tmp->this=v_from->this;
    tmp->next=v_taken;
    v_taken=tmp;
    findSubset(v_from->next,e_list,v_removed,v_taken,v_best,best_w,balance+(v_from->this->col==RED?+1:-1));
    v_taken=v_taken->next;
    tmp->next=v_removed;
    v_removed=tmp;
    findSubset(v_from->next,e_list,v_removed,v_taken,v_best,best_w,balance);
    v_removed=v_removed->next;
    free(tmp);
}

void freeListOnly(vertex_list_item_t *v){
    if(v==NULL)return;
    freeListOnly(v->next);
    free(v);
}