prim.cpp

// Author: Harsh Gupta
// Date: 12 November 2013
// Implementation of Prim's algorithm to find the minimum spanning tree
// on a Undirected Graph

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

#define V 6 // Max Size of The Matrix
const float inf = 99999;

typedef struct edge{
    int to;
    int from;
    float weight;
}edge;

typedef struct graph{
    float adjmat[V][V];
    edge edges[V*V];
    int no_edges;
}graph;

graph init_graph(graph g);
void print_graph(graph g);
/* float dist[V]; */

int is_empty(int A[], int size){
    int i;
    for(i=0;i<size;i++){
        if(A[i] != 0)
            return 0;
    }
    return 1;
}

graph add_edge(graph g, int i, int j, int cost){
    g.adjmat[i][j] = cost;
    g.adjmat[j][i] = cost;
    g.edges[g.no_edges].to= i;
    g.edges[g.no_edges].from= j;
    g.edges[g.no_edges].weight= cost;
    g.no_edges++;
    return g;
}

static int edge_comp(const void *a, const void *b){
    if(((edge*)a)->weight > ((edge*)b)->weight) return 1;
    else if(((edge*)a)->weight == ((edge*)b)->weight) return 0;
    else return -1;
}

graph sort_edges(graph g){
    qsort(g.edges, g.no_edges, sizeof(edge), edge_comp);
    return g;
}

void update_set(int A[], int size, int u, int v){
    int s_u = A[u];
    int s_v = A[v];
    for(int i=0;i<size;i++){
        if(A[i] == s_v) A[i] = s_u;
    }
}

float key[V];

int min_key_in_Q(int A[], int size){
    int i;
    float min=inf;
    int min_pos;
    for(i=0;i<size;i++){
        if(key[i] < min && A[i] == 1){
            min = key[i];
            min_pos = i;
        }
    }
    return min_pos;
}

graph init_graph(graph g){
    g.no_edges = 0;
    for(int i=0;i<V*V;i++){
        g.edges[i].to = 0;
        g.edges[i].from = 0;
        g.edges[i].weight = inf;
    }
    printf("\n");
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            g.adjmat[i][j] = inf;
        }
    }
    return g;
}

void mst_prim(graph g){
    int prev[V];
    int Q[V];
    for(int i=0;i<V;i++){
        key[i] = inf;
        Q[i] = 1;
        prev[i] = -1;
    }

    key[0] = 0;
    printf("\nPrinting the graph\n");
    print_graph(g);
    while(!is_empty(Q, V)){
        printf("in while \n");
        /* printf("T") */
        int u = min_key_in_Q(Q, V);
        Q[u] = 0;
        for(int v=0;v<V;v++){
            if(g.adjmat[u][v] < inf){
                printf("%d,%d is a edge\n",u,v);
                if(Q[v] == 1 && g.adjmat[u][v] < key[v]){
                    printf("u,v is %d %d\n",u,v);
                    prev[v] = u;
                    key[v] = g.adjmat[u][v];
                }
                else{
                    printf("u,v is %d %d and key[%d] = %0.f\n",u,v, v,key[v]);
                }
            }
            else{
                printf("(%d,%d,%0.f) is not an edge\n", u, v, g.adjmat[u][v]);
            }
        }
    }

    for(int i=1;i<V;i++){
        printf("(%d,%d,%0.f) ",i,prev[i],g.adjmat[i][prev[i]]);
    }
    printf("\n");
}
/* graph mst_prim(graph g){ */
/*     graph A; */
/*     int in_A[V]; */
/*     int Q[V]; */
/*     for(int i=0;i<V;i++){ */
/*         Q[i] = 0; */
/*         key[i] = inf; */
/*         in_A[i] = 0; */
/*     } */
/*  */
/*     Q[0] = 1; */
/*     in_A[0] = 1; */
/*     key[0] = 0; */
/*  */
/*     while(!is_empty(Q, V)){ */
/*         int u = min_key_in_Q(Q,V); */
/*         Q[u] = 0; */
/*         for(int v=0;v<V;v++){ */
/*             if(g.adjmat[u][v] !=inf){// v is adjacent to u */
/*                 #<{(| if(in_A[v] ==0 && g.adjmat[u][v] < key[v]){ |)}># */
/*                 #<{(|     Q[v] = 1; |)}># */
/*                 #<{(|     #<{(| in_A[v] = 1; |)}># |)}># */
/*                 #<{(|     key[v] = g.adjmat[u][v]; |)}># */
/*                 #<{(|     #<{(| A = add_edge(A, u, v, g.adjmat[u][v]); |)}># |)}># */
/*                 #<{(| } |)}># */
/*                 #<{(| else if(in_A[v] == 1){ |)}># */
/*                 #<{(|     Q[v] = 0; |)}># */
/*                 if() */
/*                 } */
/*             } */
/*         }//Extracting the adjacent nodes of u */
/*     } */
/* } */
/* graph mst_prim(graph g){ */
/*     #<{(| int key[V]; |)}># */
/*     graph A; */
/*     A = init_graph(A); */
/*     int in_A[V]; */
/*     #<{(| int prev[V]; |)}># */
/*     int Q[V]; */
/*     for(int i=0;i<V;i++){ */
/*         key[i] = inf; */
/*         #<{(| prev[i] = -1; |)}># */
/*         Q[i] = 1; */
/*         in_A[i] = 0; */
/*     } */
/*  */
/*     key[0] = 0; */
/*     in_A[0] = 1; */
/*     #<{(| Q[0] = 1; |)}># */
/*     while(!is_empty(Q, V)){ */
/*         int u = min_key_in_Q(Q, V); */
/*         Q[u] = 0; */
/*         for(int v=0;v<V;v++){ */
/*             if(g.adjmat[u][v] != inf && in_A[v] == 0){ */
/*                 #<{(| prev[v] = u; |)}># */
/*                 if(Q[v] == 1 && g.adjmat[u][v] < key[v]){ */
/*                     printf("Adding Edge %d, %d, %0.f\n",u,v,g.adjmat[u][v]); */
/*                     A = add_edge(A, u, v, g.adjmat[u][v]); */
/*                     key[v] = g.adjmat[u][v]; */
/*                     #<{(| Q[v] = 0; |)}># */
/*  */
/*                 } */
/*             } */
/*         } */
/*     } */
/*     return A; */
/* } */

void print_graph(graph g){
    for(int i=0;i<g.no_edges;i++){
        printf("(%d,%d,%.0f) ",g.edges[i].to,g.edges[i].from, g.edges[i].weight);
    }
    printf("\n");
    for(int i=0;i<V;i++){
        for(int j=0;j<V;j++){
            float w = g.adjmat[i][j];
            if(w !=inf)
                printf("%.0f ",w);
            else
                printf("# ");
        }
        printf("\n");
    }
}

int main(){
    graph g;
    g = init_graph(g);
    printf("Enter a connected tree of size %d\n", V);
    int u, v;
    float w;
    printf("Enter the edges in from 'to from weight' ");
    printf("Enter 0 0 0 to terminate input \n");
    /* scanf("%d %d %f", &u, &v, &w); */
    scanf("%d",&u);
    scanf("%d",&v);
    scanf("%f",&w);
    while(u !=0 || v != 0){
        g = add_edge(g, u, v, w);
        scanf("%d",&u);
        scanf("%d",&v);
        scanf("%f",&w);
    }
    print_graph(g);

    /* graph A = mst_prim(g); */
    mst_prim(g);
    /* printf("The minimum spanning tree is \n"); */
    /* print_graph(A); */
    /* g = input_graph(g); */
    /* dijkstra(g, 0); */
    /* for(int i=0;i<V;i++){ */
    /*     printf("%f ", dist[i]); */
    /* } */

    printf("\n");
    return 0;
}