DROP DATABASE spanningtree;

CREATE DATABASE spanningtree;

USE spanningtree;

/*
    A graph G is defined by its vertices and edges.
    G = (V, E).
    This program identifies vertices by a distinct numerical ID.
    These identifiers could be referenced as foreign keys for arbitrary data types.
*/
CREATE TABLE vertices (
    u INTEGER PRIMARY KEY);

/*
    An edge, in this context, is described by three elements:
    - a starting vertex, conventionally "u",
    - an ending vertex, conventionally "v",
    - and the edge "weight" or "cost," conventionally "w".
*/
CREATE TABLE edges (
    u INTEGER,
    v INTEGER,
    w INTEGER NOT NULL,
    PRIMARY KEY (u, v, w),
    FOREIGN KEY (u) REFERENCES vertices (u),
    FOREIGN KEY (v) REFERENCES vertices (u),
    CHECK (u <> v) /* Self-loops (edge u -> u) are not allowed. */);

/*
    Initially, the graph contains vertices and no edges. With no edges connecting
    vertices, all vertices exist in disjoint partitions. As edges are inserted,
    these subgraphs are joined. This concept is represented by setting the value p
    for each vertex to the numerically lowest vertex number in the partition.
    Once all vertices have the same value for p then they are members of the same
    partition, and if all vertices are joined in a single partition then the edge set E
    spans the graph G.
*/
CREATE TABLE partitions (
    u INTEGER PRIMARY KEY,
    p INTEGER,
    FOREIGN KEY (u) REFERENCES vertices (u));

/*
    The spanning *tree* is the subgrpah of G that contains exactly |V|-1 edges,
    spans G, and contains no cycle. Kruskal's algorithm uses Union-Find to initially
    classify each vertex in its distinct partition. Kruskal's algorithm inserts edges
    in ascending order by edge weight. The algorithm inserts an edge (u,v) iff u and v
    are in different partitions. The greedy decision to insert edges in ascending order
    by weight is safe by the observation that a minimum spanning tree (MST) of G can
    contain an edge that is at *least* as large as (u,v) while maintaining the desired
    properties.
*/
CREATE TABLE spanning_tree (
    u INTEGER,
    v INTEGER,
    PRIMARY KEY (u, v),
    FOREIGN KEY (u, v) REFERENCES edges (u, v));

/*
    Initialize each vertex to its own partition.
*/
delimiter //
CREATE TRIGGER default_partition AFTER INSERT ON vertices
    FOR EACH ROW
    BEGIN
        INSERT INTO partitions VALUES (NEW.u, NEW.u);
    END;//
delimiter ;

/*
    Union partitions when edges are added to the graph.
    If the vertices of the edge were previously disjoint,
    then add the edge to the spanning tree. The resulting
    spanning tree is guaranteed to be acyclic. The spanning
    tree is only guaranteed to be minimum if edges are
    inserted in order by weight (when using Kruskal's algorithm).
*/
delimiter //
CREATE TRIGGER union_partition AFTER INSERT ON edges
    FOR EACH ROW
    BEGIN
        DECLARE p1 INTEGER;
        DECLARE p2 INTEGER;
        SET p1 = (SELECT MIN(p) FROM partitions WHERE partitions.u = NEW.u OR partitions.u = NEW.v);
        SET p2 = (SELECT MAX(p) FROM partitions WHERE partitions.u = NEW.u OR partitions.u = NEW.v);
        IF p1 <> p2 THEN
            /* it is safe to insert this edge into the spanning tree */
            INSERT INTO spanning_tree VALUES (NEW.u, NEW.v);
            /* join partitions */
            UPDATE partitions SET partitions.p = p1 WHERE partitions.p = p2;
        END IF;
    END;//
delimiter ;

INSERT INTO vertices VALUES (1);
INSERT INTO vertices VALUES (2);
INSERT INTO vertices VALUES (3);
INSERT INTO vertices VALUES (4);
INSERT INTO vertices VALUES (5);
INSERT INTO vertices VALUES (6);
INSERT INTO vertices VALUES (7);
INSERT INTO vertices VALUES (8);
INSERT INTO vertices VALUES (9);

/* To execute Kruskal's algorithm, insert edges in ascending order by weight. */
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));
INSERT INTO edges VALUES (ROUND(RAND() * 9 + 1), ROUND(RAND() * 9 + 1), ROUND(RAND() * 99 + 1));

SELECT * FROM edges;
SELECT * FROM edges JOIN spanning_tree USING (u, v);
SELECT SUM(w) FROM edges JOIN spanning_tree USING (u, v);
SELECT DISTINCT p FROM partitions;