/*-
 * ----------------------------------------------------------------------------
 * "THE BEER-WARE LICENSE" (Revision 69):
 * <syrinx@FreeBSD.org> wrote this file.  As long as you retain this notice you
 * can do whatever you want with this stuff. If we meet some day, and you think
 * this stuff is worth it, you can buy me a beer in return.   -Shteryana Shopova
 * ----------------------------------------------------------------------------
 */
/*
 * Build a rootless minimal spanning tree from graph V, E
 * V = { A, B, C, D, E, F, G, H }
 * E = { e(A,G) = 1, e(B,C) = 1, e(A,H) = 2, e(C,D) = 2, 
 *	e(B,E) = 3, e(D,H) = 3, e(H,G) = 3, e(D,F) = 4,
 *	e(D,G) = 5, e(D,E) = 6, e(E,F) = 6, e(A,B) = 7,
 *	e(A,D) = 7, e(F,G) = 9 }
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <sys/queue.h>

#define NEDGES			14

struct graph;

struct gedge {
	char			vertex[2][2];
	int			cost;
	TAILQ_ENTRY(gedge)	link;
};

struct vertex {
	char			vname[2];
	struct graph		*vgraph; /* Backpointer to parent */
	STAILQ_ENTRY(vertex)	link;
};

struct graph {
	struct gedge *tqh_first;	/* first element */
	struct gedge **tqh_last;	/* addr of last next element */
	struct vertex *stqh_first;/* first element */
	struct vertex **stqh_last;
};

static struct vertex *	find_vertex(struct graph *, char *);


static struct graph *
gen_graphlist(void)
{
	int i;
	struct vertex *v;
	static struct graph g;
	static struct gedge edges[NEDGES];

	TAILQ_INIT(&g);
	STAILQ_INIT(&g);

	memset(edges, 0, NEDGES * sizeof(struct gedge));

	strcpy(edges[0].vertex[0], "F");
	strcpy(edges[0].vertex[1], "G");
	edges[0].cost = 9;

	strcpy(edges[1].vertex[0], "A");
	strcpy(edges[1].vertex[1], "D");
	edges[1].cost = 7;

	strcpy(edges[2].vertex[0], "A");
	strcpy(edges[2].vertex[1], "B");
	edges[2].cost = 7;

	strcpy(edges[3].vertex[0], "E");
	strcpy(edges[3].vertex[1], "F");
	edges[3].cost = 6;

	strcpy(edges[4].vertex[0], "D");
	strcpy(edges[4].vertex[1], "E");
	edges[4].cost = 6;

	strcpy(edges[5].vertex[0], "D");
	strcpy(edges[5].vertex[1], "G");
	edges[5].cost = 5;

	strcpy(edges[6].vertex[0], "D");
	strcpy(edges[6].vertex[1], "F");
	edges[6].cost = 4;

	strcpy(edges[7].vertex[0], "H");
	strcpy(edges[7].vertex[1], "G");
	edges[7].cost = 3;

	strcpy(edges[8].vertex[0], "D");
	strcpy(edges[8].vertex[1], "H");
	edges[8].cost = 3;

	strcpy(edges[9].vertex[0], "B");
	strcpy(edges[9].vertex[1], "E");
	edges[9].cost = 3;

	strcpy(edges[10].vertex[0], "C");
	strcpy(edges[10].vertex[1], "D");
	edges[10].cost = 2;

	strcpy(edges[11].vertex[0], "A");
	strcpy(edges[11].vertex[1], "H");
	edges[11].cost = 2;

	strcpy(edges[12].vertex[0], "B");
	strcpy(edges[12].vertex[1], "C");
	edges[12].cost = 1;

	strcpy(edges[13].vertex[0], "A");
	strcpy(edges[13].vertex[1], "G");
	edges[13].cost = 1;

	for (i = 0; i < NEDGES; i++) {
		TAILQ_INSERT_HEAD(&g, edges + i, link);
		if (find_vertex(&g, edges[i].vertex[0]) == NULL) {
			if ((v = (struct vertex *)malloc(sizeof(*v))) == NULL)
				abort();
			memset(v, 0, sizeof(*v));
			strcpy(v->vname, edges[i].vertex[0]);
			STAILQ_INSERT_HEAD(&g, v, link);
			v->vgraph = &g;
		}
		if (find_vertex(&g, edges[i].vertex[1]) == NULL) {
			if ((v = (struct vertex *)malloc(sizeof(*v))) == NULL)
				abort();
			memset(v, 0, sizeof(*v));
			strcpy(v->vname, edges[i].vertex[1]);
			STAILQ_INSERT_HEAD(&g, v, link);
			v->vgraph = &g;
		}
	}

	return (&g);
}

static int
num_vertexes(struct graph *g)
{
	int i, count = 0;
	char vnames[2 * NEDGES][2];
	struct gedge *ce;

	memset(vnames, 0, NEDGES * 4 * sizeof(char));

	TAILQ_FOREACH(ce, g, link) {
		for (i = 0; i < count; i++) {
			if (strcmp(vnames[i], ce->vertex[0]) == 0)
				break;
		}
		if (i == count) {
			strlcpy(vnames[count], ce->vertex[0], 2);
			count++;
		}
		for (i = 0; i < count; i++) {
			if (strcmp(vnames[i], ce->vertex[1]) == 0)
				break;
		}
		if (i == count) {
			strlcpy(vnames[count], ce->vertex[1], 2);
			count++;
		}
	}

	for (i = 0; i < NEDGES; i++) {
		if (vnames[i][0] == 0)
			break;
		fprintf(stderr, "Next vertex is %s\n", vnames[i]);
	}

	return (count);
}


static int
add_edge(struct gedge *e, struct graph *g)
{
	struct gedge *tmp;

	if ((tmp = (struct gedge *)malloc(sizeof(*tmp))) == NULL)
		return (-1);

	memset(tmp, 0, sizeof(*tmp));
	strcpy(tmp->vertex[0], e->vertex[0]);
	strcpy(tmp->vertex[1], e->vertex[1]);
	tmp->cost = e->cost;

	TAILQ_INSERT_HEAD(g, tmp, link);

	return (0);
}

static void
print_graph(struct graph *g)
{
	struct gedge *ce;

	TAILQ_FOREACH(ce, g, link)
		fprintf(stderr, "Vertexes { %s, %s }, edge cost %d\n",
		    ce->vertex[0], ce->vertex[1], ce->cost);
}

static struct graph *
find_tree(struct graph **g, char *vname, int count)
{
	int i;
	struct vertex *v;
	struct graph *t = *g;

	for (i = 0; i < count; i++, t++) {
		STAILQ_FOREACH(v, t, link)
			if (strcmp(vname, v->vname) == 0)
				return (t);
	}

	return (NULL);
}

static struct vertex *
find_vertex(struct graph *g, char *vname)
{
	struct vertex *v;

	STAILQ_FOREACH(v, g, link)
		if (strcmp(vname, v->vname) == 0)
			return (v);

	return (NULL);
}

int
main(int argc, char **argv, char **envp)
{
	int i, count;
	struct gedge *ce;
	struct vertex *v, *vt;
	struct graph *tt, *pt, *t1, *t2, *g = gen_graphlist();

	count = num_vertexes(g);
	fprintf(stderr, "Number of vertexes is %d\n",count);

	if ((tt = (struct graph *)malloc(count * sizeof(*tt))) == NULL)
		abort();

	/* 1. Build trivial trees for each vertex */
	pt = tt;
	STAILQ_FOREACH(v, g, link) {
		TAILQ_INIT(pt);
		STAILQ_INIT(pt);

		if ((vt = (struct vertex *)malloc(sizeof(*vt))) == NULL)
			abort();
		memset(vt, 0, sizeof(*vt));
		strcpy(vt->vname, v->vname);
		STAILQ_INSERT_HEAD(pt, vt, link);
		vt->vgraph = pt;
		fprintf(stderr, "Build trivial tree %d with vertex %s\n", (unsigned int) (pt - tt), v->vname);
		pt++;
	}

	TAILQ_FOREACH(ce, g, link) {
		/* Find the tree in which each vetrex of the edge is */
		t1 = find_tree(&tt, ce->vertex[0], count);
		t2 = find_tree(&tt, ce->vertex[1], count);

		fprintf(stderr, "Vertexes %s, %s in trees 0x%x, 0x%x\n",
			    ce->vertex[0], ce->vertex[1], (unsigned int) (t1 - tt), (unsigned int) (t2 - tt));
		
		if (t1 == NULL || t2 == NULL)
			abort();

		if (t1 != t2) {
			fprintf(stderr, "Vertexes %s, %s in different trees - merge\n",
			    ce->vertex[0], ce->vertex[1]);

			STAILQ_FOREACH(v, t2, link) {
				fprintf(stderr, "Move vertex %s from tree %d to tree %d\n",
					vt->vname, (unsigned int)(t2 - tt), (unsigned int) (t1 - tt));
				v->vgraph = t1;
			}

			TAILQ_CONCAT(t1, t2, link);
			STAILQ_CONCAT(t1, t2);

			(void)add_edge(ce, t1);
		}
	}

	fprintf(stderr, "The minimal spanning tree for the graph is\n");
	for (i = 0, pt = tt; i < count; i++, pt++) {
		if (STAILQ_EMPTY(pt)) {
			fprintf(stderr, "The tree %d is empty\n", i);
			continue;
		}
		fprintf(stderr, "Found tree %d not empty\n", i);
		print_graph(pt);
	}

	/* XXX: FIXME - free all allocated resources */

	exit(0);
}