Created
May 26, 2017 16:23
-
-
Save chris373/fa1825b8368a0219a0f9d6d70e63be10 to your computer and use it in GitHub Desktop.
Kruskal Algorithm
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package com.mygdx.game; | |
| import com.badlogic.gdx.math.Vector2; | |
| import com.badlogic.gdx.utils.ShortArray; | |
| import java.util.*; | |
| public class KruskalAlgorithm { | |
| public Vector2[] kruskal_from_triangles(ShortArray triangles, float[] points) { | |
| // transform into vertices for kruskal's algorithm | |
| ArrayList<Vector2> vertices = new ArrayList<>(); | |
| ArrayList<Vector2> edges = new ArrayList<>(); | |
| for(int i = 0; i < points.length; i += 2) { | |
| Vector2 vertice = new Vector2(points[i], points[i + 1]); | |
| vertices.add(vertice); | |
| System.out.println("point " + points[i] + " " + points[i+1]); | |
| } | |
| for (int i = 0; i < triangles.size; i += 3) { | |
| int p1 = triangles.get(i) * 2; | |
| int p2 = triangles.get(i + 1) * 2; | |
| int p3 = triangles.get(i + 2) * 2; | |
| Vector2 a = new Vector2(points[p1], points[p1 + 1]); | |
| Vector2 b = new Vector2(points[p2], points[p2 + 1]); | |
| Vector2 c = new Vector2(points[p3], points[p3 + 1]); | |
| edges.add(a); edges.add(b); | |
| edges.add(b); edges.add(c); | |
| edges.add(c); edges.add(a); | |
| } | |
| return this.kruskal(vertices.toArray(new Vector2[vertices.size()]), edges.toArray(new Vector2[edges.size()])); | |
| } | |
| class Edge implements Comparator<Edge> { | |
| Vector2 v1; | |
| Vector2 v2; | |
| float length; | |
| Edge(Vector2 v1, Vector2 v2) { | |
| this.v1 = v1; | |
| this.v2 = v2; | |
| this.length = v1.dst(v2); | |
| } | |
| Edge() { | |
| } | |
| @Override | |
| public int compare(Edge e1, Edge e2) { | |
| if (e1.length > e2.length) return 1; | |
| else if (e1.length < e2.length) return -1; | |
| else return 0; | |
| } | |
| } | |
| /* | |
| Algorithm | |
| create a forest F (a set of trees), where each vertex in the graph is a separate tree | |
| create a set S containing all the edges in the graph | |
| while S is nonempty and F is not yet spanning | |
| remove an edge with minimum weight from S | |
| if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree | |
| At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, | |
| the forest has a single component and forms a minimum spanning tree | |
| */ | |
| // edges are represented by two consecutive vectors that are the points it connects. | |
| public Vector2[] kruskal(Vector2[] vertices, Vector2[] edges) { | |
| ArrayList<Vector2> minimum_spanning_tree = new ArrayList<>(); | |
| TreeSet<Edge> S = new TreeSet<Edge>(new Edge()); | |
| ArrayList<Vector2> F = new ArrayList<>(); | |
| HashMap<Vector2, Integer> treeids = new HashMap<>(); | |
| HashMap<Integer, ArrayList<Vector2>> trees = new HashMap<>(); | |
| // give each tree an id based on the vertex reference | |
| int treeid = 0; | |
| // create and edge for each pair of vertexes in edges and add it to S | |
| for(int i = 0; i < edges.length; i += 2) { | |
| Edge e = new Edge(edges[i], edges[i+1]); | |
| S.add(e); | |
| } | |
| while (S.size() > 0 && F.size() < vertices.length) { | |
| Edge min = S.pollFirst(); | |
| Vector2 v1 = min.v1; | |
| Vector2 v2 = min.v2; | |
| if (! treeids.containsKey(v1)) { | |
| // create a treeid for v, create a tree for that id, add v to it. | |
| treeids.put(v1, treeid); | |
| trees.put(treeid, new ArrayList<>()); | |
| trees.get(treeid).add(v1); | |
| treeid++; | |
| } | |
| if (! treeids.containsKey(v2)) { | |
| // create a treeid for v, create a tree for that id, add v to it. | |
| treeids.put(v2, treeid); | |
| trees.put(treeid, new ArrayList<>()); | |
| trees.get(treeid).add(v2); | |
| treeid++; | |
| } | |
| int v1id = treeids.get(v1); | |
| int v2id = treeids.get(v2); | |
| // test for connection of separate trees | |
| if (v1id != v2id) { | |
| minimum_spanning_tree.add(v1); | |
| minimum_spanning_tree.add(v2); | |
| // vector -> tree id -> tree | |
| ArrayList<Vector2> v1trees = trees.get(treeids.get(v1)); | |
| ArrayList<Vector2> v2trees = trees.get(treeids.get(v2)); | |
| // add v2 trees to v1trees, and set the id for v2 tree to point to v1's tree | |
| for (Vector2 c2: v2trees) { | |
| v1trees.add(c2); | |
| System.out.println("changing " + treeids.get(c2) + " to " + v1id); | |
| treeids.put(c2, v1id); | |
| } | |
| F = v1trees; | |
| } | |
| } | |
| System.out.println("minimum spanning tree length " + minimum_spanning_tree.size()); | |
| int size = minimum_spanning_tree.size(); | |
| return minimum_spanning_tree.toArray(new Vector2[size]); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment