Kruskal_Processing

0_Kruskal_Processing.pde

import java.util.Collections;
import java.util.Comparator;

final int N_NODES = 128;
int nodeCount = 0;
ArrayList<Node> nodes = new ArrayList();
ArrayList<Edge> edges = new ArrayList();
ArrayList<Edge> mst = new ArrayList();

void setup() {
  size(1024, 1024);
  background(0);
  for (int i = 0; i < N_NODES; i++) {
    nodes.add(new Node(int(random(16, width-16)), int(random(16, height-16))));
  }

  MSTKruskal(nodes);

  for (Edge e : edges) {
    stroke(255, 10);
    e.draw();
  }

  for (Edge e : mst) {
    stroke(255);
    e.draw();
  }

  for (Node n : nodes) {
    stroke(255);
    strokeWeight(8);
    n.draw();
  }

  noLoop();
   saveFrame("kruskal.png");

}

void MSTKruskal(ArrayList<Node> nodes) {

  for (Node a : nodes) {
    for (Node b : nodes) {
      if (a.id < b.id)
        edges.add(new Edge(a, b));
    }
  }

  DisjointSet grouping = new DisjointSet(edges.size());

  Collections.sort(edges);

  for (Edge e : edges) {
    if (grouping.find(e.a.id) != grouping.find(e.b.id)) {
      mst.add(new Edge(e.a, e.b));
      grouping.union(e.a.id, e.b.id);
    }
  }
  
}

1_DisjointSet.pde

class DisjointSet {
  int parent[];
  DisjointSet(int size) {
    parent = new int[size];
    for (int i = 0; i < size; i++)
      parent[i] = i;
  }
  int find(int x) {
    if (parent[x] != x)
      parent[x] = find(parent[x]);  // path compression
    return parent[x];
  }
  void union(int x, int y) {
    parent[find(x)] = find(y);
  }
}

2_Node.pde

class Node {
  float x, y;
  int id;
  
  Node(int x, int y) {
    this.x = x;
    this.y = y;
    this.id = nodeCount++;
  }
  void draw() {
    point(this.x,this.y);
  }
}

3_Edge.pde

public class Edge implements Comparable<Edge> {

  float distSq;
  Node a, b;

  Edge(Node a, Node b) {
    this.a = a;
    this.b = b;
    float dx = a.x - b.x;
    float dy = a.y - b.y;
    distSq = dx * dx + dy * dy;
  }

  @Override
    public int compareTo(Edge _e) {

    if (this.distSq > _e.distSq) {
      return 1;
    } else if (this.distSq < _e.distSq) {
      return -1;
    } else {
      return 0;
    }
  }

  void draw() {
    line(this.a.x, this.a.y, this.b.x, this.b.y);
  }
}