20150223 my solution

20150223.c

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

#define dieIf(a,b) if(a){printf(b);exit(EXIT_FAILURE);}

typedef struct v_list_t v_list_t;
typedef struct v_t v_t;
typedef struct e_t e_t;
typedef struct path_t path_t;
typedef struct v_table_t v_table_t;

struct v_list_t{
    v_list_t *next;
    v_t *this;
};

struct v_t{
    char *name;
    int visited;
    int h_index;
    e_t *edges;
};

struct e_t{
    int weight;
    v_t *v;
    e_t *next;
};

struct path_t{
    v_list_t *v_stack;
    int weight,k,p;
    v_t *dest;
};

struct v_table_t{
    char **name;
    v_t **this;
    int size;
};

void *allocateOrDie(size_t size);
path_t *pathFinder(v_list_t *vertices, v_table_t *v_table, char *s_name, char *d_name, int k, int p);
void pathFinder_r(path_t *path, path_t *best, int k, int p);
v_list_t *loadVertices(FILE *input,v_table_t **v_table);
void copyPath(path_t *to, path_t *from);
v_table_t *v_tableInit(int N);
int v_tableInsert(v_table_t *v_table, char *name, v_t *pointer);
v_t *v_tablePointerByName(v_table_t *v_table, char *name);
void addEdge(v_t *from, v_t *to);
void fprintStackBottomUp(FILE *output, v_list_t *stack);
v_t *initVertex(v_list_t *vertices, v_table_t *v_table, char *v_name);
path_t *pathInit();

int main(int argc, char **argv){
    FILE *input, *output;
    v_list_t *vertices;
    path_t *path;
    int k,p;
    char start[20+1], dest[20+1];
    v_table_t *v_table;

    dieIf(argc!=3,"Run as: program.exe <input_file> <output_file>\n");

    input=fopen(argv[1],"r");
    dieIf(input==NULL,"Can NOT open input file.\n");

    vertices=loadVertices(input,&v_table);

    fclose(input);

    printf("Insert names of start and destination: ");
    scanf("%s %s",start,dest);
    printf("Insert values for k and p: ");
    scanf("%d %d",&k,&p);

    path=pathFinder(vertices,v_table,start,dest,k,p);

    if(path->v_stack==NULL)printf("No path exists for this parameters.\n");
    else{
        output=fopen(argv[2],"w");
        dieIf(output==NULL,"Can NOT open output file.\n");

        fprintStackBottomUp(output,path->v_stack);
    }

    return 0;
}

void *allocateOrDie(size_t size){
    void *item=malloc(size);
    dieIf(item==NULL,"Failure allocating memory.\n");
    return item;
}

v_list_t *loadVertices(FILE *input, v_table_t **v_table){
    v_list_t *vertices;
    char v1_name[20+1], v2_name[20+1];
    v_t *v1,*v2;
    int w;
    int count=0;

    while(fscanf(input,"%*s %*d %*s")==3)count++;
    *v_table=v_tableInit(count*4);

    rewind(input);
    while(fscanf(input,"%s %d %s",v1_name,&w,v2_name)==3){
        v1=v_tablePointerByName(*v_table,v1_name);
        if(v1==NULL)v1=initVertex(vertices,*v_table,v1_name);
        v2=v_tablePointerByName(*v_table,v2_name);
        if(v2==NULL)v2=initVertex(vertices,*v_table,v2_name);
        addEdge(v1,v2);
    }
}

path_t *pathFinder(v_list_t *vertices, v_table_t *v_table, char *s_name, char *d_name, int k, int p){
    v_t *s,*d;
    path_t *path,*best;

    s=v_tablePointerByName(v_table,s_name);
    dieIf(s==NULL,"Start vertex does not exist.\n");
    d=v_tablePointerByName(v_table,d_name);
    dieIf(d==NULL,"Destination vertex does not exist.\n");

    path=pathInit();
    path->dest=d;
    best=pathInit();

    pathFinder_r(path,best,k,p);

    return best;
}

void pathFinder_r(path_t *path, path_t *best, int k, int p){
    e_t *tmp;
    v_list_t *next_step;
    v_t *actual=path->v_stack->this;

    if(actual==path->dest){
        if(path->weight>best->weight)copyPath(best,path);
        return;
    }

    if(path->k>k)return;
    if(path->p>p)return;

    next_step=(v_list_t*)allocateOrDie(sizeof(v_list_t));
    next_step->next=path->v_stack;
    path->v_stack=next_step;

    for(tmp=actual->edges;tmp!=NULL;tmp=tmp->next){
        path->v_stack->this=tmp->v;
        path->weight+=tmp->weight;
        tmp->v->visited++;
        if(tmp->v->visited==2)path->k++;
        if(tmp->v->visited!=1)path->p++;

        pathFinder_r(path,best,k,p);

        if(tmp->v->visited==2)path->k--;
        if(tmp->v->visited!=1)path->p--;
        tmp->v->visited--;
        path->weight-=tmp->weight;
    }

    path->v_stack=path->v_stack->next;
    free(next_step);
}