/* 
 * Code example for CP264 Data Structures II
 * Prim's algorithn for MST
 * from textbook
*/

#include<stdio.h>

#define INFINITY 9999
#define MAX 10
int adj[MAX][MAX], tree[MAX][2], n = MAX;

void test_graph();
void random_graph(int);
void readmatrix();
void display_graph();
int mst_prim(int src);
void display_tree();

int main() {
  test_graph();
  display_graph();
  mst_prim(0);
  display_tree();
  return 0;
}

void test_graph() {
  n = 5;
  int i, j;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      adj[i][j] = INFINITY;
    }
  }

  adj[0][1] = 7;
  adj[1][0] = 7;
  adj[0][2] = 3;
  adj[2][0] = 3;
  adj[1][2] = 4;
  adj[2][1] = 4;
  adj[2][3] = 10;
  adj[3][2] = 10;
  adj[1][3] = 9;
  adj[3][1] = 9;
  adj[1][4] = 11;
}

void random_graph(int nc) {
  int i, j;
  for (i = 0; i < nc; i++) {
    for (j = 0; j < i; j++) {
      if (j == i) {
        adj[i][j] = 0;
      } else {
        adj[i][j] = rand() % 20;
        adj[j][i] = adj[i][j];
      }
    }
  }
}

void display_graph() {
  int i, j;
  printf("   ");
  for (i = 0; i < n; i++)
    printf("%-5d ", i);
  printf("\n");
  for (i = 0; i < n; i++) {
    printf("%d ", i);
    for (j = 0; j < n; j++) {
      printf(" %-5d", adj[i][j]);
    }
    printf("\n");
  }
}

void readmatrix() {
  int i, j;
  printf("\nEnter the number of nodes in the Graph : ");
  scanf("%d", &n);
  printf("\nEnter the adjacency matrix of the Graph");
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) {
      scanf("%d", &adj[i][j]);
      adj[j][i] = adj[i][j];
    }
}

int mst_prim(int src) {
  int visited[MAX], d[MAX], parent[MAX];
  int i, j, min, u, v, cost=0;

  for (i = 0; i < n; i++) {
    d[i] = adj[src][i];
    visited[i] = 0;
    parent[i] = src;
  }

  visited[src] = 1;

  for (i = 0; i < n-1; i++) {
    min = 9999;

    //extract minimum key node 
    for (j = 0; j < n; j++) {
      if (visited[j] == 0 && d[j] < min) {
        min = d[j];
        u = j;
      }
    }
    visited[u] = 1;
    tree[i][0] = parent[u];
    tree[i][1] = u;
    cost += min;

    //decrease key
    for (v = 0; v < n; v++) {
      if (visited[v] == 0 && adj[u][v] < d[v] ) {
        d[v] = adj[u][v];
        parent[v] = u;
      }
    }
  }
  return cost;
}

void display_tree() {
  int i, cost = 0;
  printf("\nThe edges of the MST are");
  for (i = 0; i < n-1; i++) {
    printf("\n%d %d", tree[i][0], tree[i][1]);
    cost += adj[tree[i][0]][tree[i][1]];
  }
  printf("\nThe total cost of the MST is %d", cost);
}


/*
   0     1     2     3     4
0  9999  7     3     9999  9999
1  7     9999  4     9     11
2  3     4     9999  10    9999
3  9999  9     10    9999  9999
4  9999  9999  9999  9999  9999

The edges of the MST are
0 2
2 1
1 3
1 4
The total cost of the MST is 27

 */