pal hw03

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   main.c
 * Author: Jan
 *
 * Created on November 18, 2016, 3:15 PM
 */

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

#define CONSOLE 0

struct Edge {
    int start;
    int end;
    int cost;
    int component;
};

int recursive(int n, int k);
int print_arr(int arr[], int k);
int my_compare(struct Edge * e1, struct Edge * e2);

struct Edge * edges_ground;
struct Edge * edges_bet;
int * components;
int * used_vertices;
int edges_ground_num = 0;
int edges_bet_num = 0;
int v_num, e_num, bet_num, bet_total, border;
int best_cost = INT_MAX;


int main(int argc, char** argv) {
    int i, j, start_tmp, end_tmp, cost_tmp;




#if CONSOLE
    /*READ FROM INPUT*/

    scanf("%d", &v_num);
    scanf("%d", &e_num);

    int * data = (int *) malloc(e_num * 3 * sizeof(int));
    stack =  (int *) malloc(v_num * sizeof(int));

    for(i = 0; i < e_num*3; i++){
        scanf("%d", data + i);
    }

#else
    /*
        1 - 30
        2 - 21
        3 - 59
        4 - 270
        5 - 126
        6 - 87653
        7 - 3254
        8 - 16962
        9 - 6633
        10 - 522203
        */

    /*READ FROM FILE*/
    FILE* file;
    file = fopen("./data/pub09.in", "r");
    fscanf(file, "%d", &e_num);
    fscanf(file, "%d", &v_num);
    fscanf(file, "%d", &border);
    fscanf(file, "%d", &bet_num);

    printf("total number of edges        = %d\n", e_num);
    printf("total number of vertices     = %d\n", v_num);
    printf("total number of border edges = %d\n", bet_num);
    printf("bet index                    = %d\n", border);

//    int edges_ground_num = 0;
//    int edges_bet_num = 0;

    edges_ground = (struct Edge *) malloc(e_num * sizeof(struct Edge));
    edges_bet = (struct Edge *) malloc(e_num * sizeof(struct Edge));
    components = (int *) malloc(v_num * sizeof(int));
    used_vertices = (int *) malloc(v_num * sizeof(int));
//    components = (int *) calloc(v_num, sizeof(int));
//    used_vertices = (int *) calloc(v_num, sizeof(int));


    /* read file and split the edges */
    for(i = 0; i < e_num; i++){
        fscanf(file, "%d", &start_tmp);
        fscanf(file, "%d", &end_tmp);
        fscanf(file, "%d", &cost_tmp);
        if((start_tmp <= border && end_tmp <= border) || (start_tmp > border && end_tmp > border)){
            struct Edge * e = &edges_ground[edges_ground_num];
            e->start = start_tmp;
            e->end = end_tmp;
            e->cost = cost_tmp;
            edges_ground_num++;
        } else {
            struct Edge * e = &edges_bet[edges_bet_num];
            e->start = start_tmp;
            e->end = end_tmp;
            e->cost = cost_tmp;
            edges_bet_num++;
        }
    }

    fclose(file);


#endif

    qsort(edges_ground, edges_ground_num, sizeof(struct Edge), my_compare);

    /* read file and split the edges */
    for(i = 0; i < edges_bet_num; i++){
//        printf("edge between [%d, %d, %d]\n", edges_bet[i].start, edges_bet[i].end, edges_bet[i].cost);
    }
    for(i = 0; i < edges_ground_num; i++){
//        printf("edge ground  [%d, %d, %d]\n", edges_ground[i].start, edges_ground[i].end, edges_ground[i].cost);
    }

//    printf("starting recursive\n");
    recursive(edges_bet_num, bet_num);


    printf("%d", best_cost);
    return (EXIT_SUCCESS);
}

int cruscal(int arr[]){
//    printf("STARTING CRUSCAL\n");
//    print_arr(arr, bet_num);
    int i, j, start, end, c_start, c_end;
    int cost_total = 0, used_edges = 0, starting_idx = 0, starting = 1, used_vertices_num = 0;
    int component_num = 0;
    int edge_idx = 0;
    for(i = 0; i < v_num; i++) {components[i] = -3;}
    for(i = 0; i < v_num; i++) {used_vertices[i] = -2;}

//    printf("edges_ground_num %d\n", edges_ground_num);

    struct Edge * edge;
    while(used_edges < v_num - 1){
//        printf("--%d, used edges %d / %d, st idx %d, st %d, c %d -- \n", edge_idx, used_edges, edges_ground_num, starting_idx, starting, cost_total);
//        print_arr(components, v_num);
//        print_arr(used_vertices, v_num);

        if(starting_idx >= bet_num) starting = 0;
        if(starting){
//            printf("starting true\n");
//                e = betEdgesPossible.get(arr[starting_idx]);
            edge = &edges_bet[arr[starting_idx]];  // check
            starting_idx++;
        } else{
            if(edge_idx == edges_ground_num) {
//                printf("NOT FEASIBLE SOLUTION");
                return INT_MAX;
            }
            edge = &edges_ground[edge_idx];   // check
            edge_idx++;
        }
        start = edge->start;
        end = edge->end;
//        printf("chosen [%d, %d, %d], %p\n", start, end, edge->cost, edge);
        c_start = (components[start] >= 0) ? 1 : 0;
        c_end = (components[end] >= 0) ? 1 : 0;
//        printf("[%d, %d]\n", start, end);

        if(c_start && c_end){ // if edges are both in existing components
            if(components[start] == components[end]){
                if(starting){
                    cost_total += edge->cost;
                }
//                printf("skipping\n");
                continue;
            } else{
                int end_comp = components[end];
                int start_comp = components[start];
                int idx;
//                printf("adding edge [%d %d %d] connecting %d and %d\n", start, end, edge->cost, start_comp, end_comp);
                for(j = 0; j < used_vertices_num; j++){
                    idx = used_vertices[j];
                    if(components[idx] == end_comp) components[idx] = start_comp;
                }
                used_edges++;
            }
        } else if(c_start && !c_end){
//            printf("adding edge [%d %d %d] 1sided1\n", start, end, edge->cost);
            components[end] = components[start];
            used_edges++;
            used_vertices[used_vertices_num] = end;
            used_vertices_num++;
        } else if(!c_start && c_end){
//            printf("adding edge [%d %d %d] 1sided2\n", start, end, edge->cost);
//            printf("x\n");
//            printf("x4\n");
//            printf("component start %d end %d\n", components[start], components[end]);
            int tmp = components[end];
            components[start] = tmp;
            used_edges++;
            used_vertices[used_vertices_num] = start;
            used_vertices_num++;
        } else{
//            printf("adding edge [%d %d %d] alone\n", start, end, edge->cost);

            components[start] = component_num;
            components[end] = component_num;

            used_edges++;
            component_num++;
            used_vertices[used_vertices_num] = start;
            used_vertices[used_vertices_num+1] = end;
            used_vertices_num += 2;
        }
        cost_total += edge->cost;
    }

    for(i = 0; i < e_num; i++) {used_vertices[i] = -1;}
    //clear chosen_vertices
//    printf("cost %d\n", cost_total);
    return cost_total;
}



int recursive(int n, int k){
    int arr[k];
    int index = 0;
    int i = 0;

    while(index >= 0){
        if(i > (n + (index - k))){
            index--;
            if(index <= 0){
                i = arr[0]+1;
            } else {
                i = arr[index]+1;
            }
        } else{
            arr[index] = i;
            if(index == k-1){
                int cost = cruscal(arr);
                best_cost = (cost < best_cost) ? cost : best_cost;
                i++;
            }
            else{
                i = arr[index]+1;
                index++;
            }
        }
    }
}

int print_arr(int arr[], int k){
    int i;
    printf("array: [");
    for(i = 0; i < k; i++){
        printf("%d ", arr[i]);
    }printf("]\n");
}

int my_compare(struct Edge * e1, struct Edge * e2){
    return e1->cost - e2->cost;
}