/*
 * Experiment with union-find, from Course notes, page 389
 */

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

/*
 * As edges are added, a vertex belongs to some
 * tree of connected edges
 */
struct tree {
    int root, length, next;
};


/* The collection of connected trees form a forest */
struct tree *forest;


/* an edge is a pair of vertices and a weight */
struct edge {
  int v1, v2, weight;
};


/*
 * find a minimum spanning tree for adj_mat
 * which must be a connected, weighted,
 * undirected graph.  Non-edges indicated by INT_MAX
 */
extern struct edge *kruskal(int **adj_mat, int vertexcount);


int main()
{
  int i;
  struct edge *spanning_tree;
  int** adj_mat = (int **) malloc (4 * sizeof(int *));
  for (i = 0; i < 4; i++)
    adj_mat[i] = (int *) malloc(4 * sizeof(int));

  adj_mat[0][0] = INT_MAX;
  adj_mat[0][1] = INT_MAX;
  adj_mat[0][2] = 2;
  adj_mat[0][3] = 1;

  adj_mat[1][0] = INT_MAX;
  adj_mat[1][1] = INT_MAX;
  adj_mat[1][2] = 4;
  adj_mat[1][3] = INT_MAX;

  adj_mat[2][0] = 2;
  adj_mat[2][1] = 4;
  adj_mat[2][2] = INT_MAX;
  adj_mat[2][3] = 3;

  adj_mat[3][0] = 1;
  adj_mat[3][1] = INT_MAX;
  adj_mat[3][2] = 3;
  adj_mat[3][3] = INT_MAX;

  spanning_tree = kruskal(adj_mat, 4);

  for (i = 0; i < 3; i++)
    printf("(%d,%d)\n", spanning_tree[i].v1,
	   spanning_tree[i].v2);

  free(spanning_tree);
  free(adj_mat);
  return 0;
}


struct edge *kruskal(int **adj_mat, int vertexcount)
{
  struct edge *all_edges, *spanning_edges;
  int edges_found = 0, edgecount, i;
  void sort_edges(struct edge *edgelist, int from, int to);
  struct edge *init_edges(int **adj_mat, int vertexcount, int *edgecount);
  void init_forest(int vertex_count);
  int root_of(int node_index);
  void add_edge(int i, int j);

  spanning_edges = (struct edge *)
    malloc((vertexcount - 1) * sizeof(struct edge));
  all_edges = init_edges(adj_mat, vertexcount, &edgecount);
  sort_edges(all_edges, 0, edgecount - 1);
  init_forest(vertexcount);
  for (i = 0; i < edgecount && edges_found < vertexcount - 1; i++) {
    if (root_of(all_edges[i].v1) != root_of(all_edges[i].v2)) {
      spanning_edges[edges_found] = all_edges[i];
      add_edge(all_edges[i].v1, all_edges[i].v2);
      edges_found++;
    }
  }
  free(forest);
  free(all_edges);
  return spanning_edges;
}


void sort_edges(struct edge *edgelist, int from, int to)
{
  int pivot_index;
  int select_and_shuffle(struct edge *edgelist, int from, int to);

  pivot_index = select_and_shuffle(edgelist, from, to);

  if (pivot_index > from)
    sort_edges(edgelist, from, pivot_index - 1);
  if (pivot_index < to)
    sort_edges(edgelist, pivot_index + 1, to);
}


int select_and_shuffle(struct edge *edgelist, int from, int to)
{
  int leq = from, i, pivot = edgelist[from].weight;
  struct edge tmpEdge;

  for (i = from + 1; i <= to; i++) {
    if (edgelist[i].weight <= pivot) {
      leq++;
      tmpEdge = edgelist[i];
      edgelist[i] = edgelist[leq];
      edgelist[leq] = tmpEdge;
    }
  }
  tmpEdge = edgelist[from];
  edgelist[from] = edgelist[leq];
  edgelist[leq] = tmpEdge;
  return leq;
}


struct edge *init_edges(int **adj_mat, int vertexcount, int *edgecount)
{
  int i, j, k = 0;
  struct edge *edges;

  *edgecount = 0;
  for (i = 0; i < vertexcount; i++) {
    for (j = i; j < vertexcount; j++) {
      if (adj_mat[i][j] != INT_MAX)
	*edgecount += 1;
    }
  }

  edges = (struct edge *) malloc(*edgecount * sizeof(struct edge));
  for (i = 0; i < vertexcount; i++) {
    for (j = i; j < vertexcount; j++) {
      if (adj_mat[i][j] != INT_MAX) {
	edges[k].v1 = i;
	edges[k].v2 = j;
	edges[k].weight = adj_mat[i][j];
	k++;
      }
    }
  }
  return edges;
}


void init_forest(int vertex_count)
{
    int i;
    forest = (struct tree *)
	malloc(vertex_count * sizeof(struct tree));

    for (i = 0; i < vertex_count; i++) {
	forest[i].root = forest[i].next = i;
	forest[i].length = 1;
    }
}


int root_of(int node_index)
{
    return forest[node_index].root;
}


void add_edge(int i, int j)
{
  void merge_trees(int c1, int c2);

    if (forest[i].root == forest[j].root)
	return;
    else if (forest[forest[i].root].length <
	     forest[forest[j].root].length)
	merge_trees(i, j);
    else
	merge_trees(j, i);
}


void merge_trees(int c1, int c2)
{
    int i, j, oldroot = forest[c2].root, tmp;
    forest[forest[c1].root].length +=
	forest[oldroot].length;
    for (i = oldroot, j = 0; j < forest[oldroot].length;
	 i = forest[i].next, j++)
	forest[i].root = forest[c1].root;
    /* make the circle longer */
    tmp = forest[c1].next;
    forest[c1].next = forest[oldroot].next;
    forest[oldroot].next = tmp;
}