In this project, you will implement the Prim and Kruskal algorithms for Minimum spanning trees according to the outline given in class. Some of the details of that outline are repeated here.
A weighted graph will be represented a list of weighted edges. The WEdge class represents a weighted edge in a graph.
public class WEdge implements Comparable<WEdge> { public final int weight; // weight of edge public final int u, v; // endpoints of edge public WEdge(int u, int weight, int v) { this.u = Math.min(u, v); this.v = Math.max(u, v); this.weight = weight; } @Override public String toString() { return String.format("(%d, %d, %d)", u, weight, v); } @Override public boolean equals(Object other) { if (!(other instanceof WEdge) ) return false; WEdge e = (WEdge)other; return e.u == u && e.v == v || e.u == v && e.v == u; } @Override public int hashCode() { int hash = 5; hash = 97 * hash + this.u; hash = 97 * hash + this.v; return hash; } @Override public int compareTo(WEdge o) { return weight - o.weight; } }
Here is an example of the contents of such a file:
9 15 0 2 1 1 4 2 1 6 6 0 3 6 6 3 7 6 1 8 8 4 7 7 2 2 7 8 3 3 2 2 4 1 3 8 2 4 5 6 4 5 5 8 5 7 0
The graph in this file has 9 vertices and 15 edges.
Create a Prim class with a static method
static ListgetMST(List graph, int numberVertices)
that takes as parameter a list of weighted edges representing a graph, and an integer representing the number of vertices of the graph. The method returns a list of weighted edges that represents a minimum spanning tree of the graph that was passed in as parameter.
As part of your algorithm, keep an array of boolean value, indexed by the set of vertices, that indicates whether a particular vertex is in the tree being assembled by Prim's algorithm.
boolean [] inTree = new int[numberVertices];
Create a class Kruskal with a static method
static ListgetMST(List graph, int numberVertices)
that takes as parameter a list of weighted edges representing a graph, and an integer representing the number of vertices of the graph. The method returns a list of weighted edges that represents a minimum spanning tree of the graph that was passed in as parameter.
Kruskal functions by maintaining a forest of trees that is known to be a part of a minimum spanning tree. Initially you have N trees, with each tree consisting of a single vertex. Kruskal proceeds by adding edges to the forest of trees, in such a way that each edge added combines the two trees containing the end points of the edge being added into one tree. To avoid adding a cycle, the endpoints of the edge must be in two different trees of the spanning forest. We need a data structure that can quickly tell is if trees containing the endpoints of the edge are distinct, or the same tree. Do this by using an array that assigns to each vertex a label such that all vertices in the same tree component are assigned the same label. Originally, each vertex is labeled by itself:
int [] label = new int[numberVertices]; for (int k = 0; k < label.length; k++) { label[k] = k; }
When you combine two trees, assign to all vertices in the combined true the minimum label of all vertices in the two trees. Thus, if e is an edge being considered for adding to the forest, you want to make sure that label[e.u], the label of one of the endpoints in the edge e, is different from label[e.v], the label of the other endpoint of the edge.
Write a class GraphUtils class that contains two static methods
class GraphUtils { /** * Opens a file and reads data describing a weighted graph. * The file starts with the number of vertices in the graph, * followed by the number of edges Y, followed by Y triples giving * the an endpoint u, a weight, and another endpoint v of a weighted edge * @param graphEdges: Adds all WEdge objects collected from the file to this list. * @return the number of vertices in the graph. * @throws FileNotFoundException */ static int getWeightedGraphFromFile(List<eWEdge> graphEdges) throws FileNotFoundException { // Your code here return ?; } /** * * @param graphEdges * @return total weight of all edges in the graph */ static int totalWeight(List<eWEdge> graphEdges) { return ?; } }
One method is to gather the graph information from a file, and the other is to compute the total weight of a list of edges.
Put all code in a single project. To test your method, use the following main program.
import java.io.FileNotFoundException; import java.util.LinkedList; import java.util.List; /** * * @author gcm */ public class MinSpanningTrees { public static void main(String[] args) throws FileNotFoundException { List<WEdge> graphEdges = new LinkedList<>(); int numberVertices = GraphUtils.getWeightedGraphFromFile(graphEdges); System.out.println("The edges of the graph are: \n" + graphEdges); List%ltWEdge> spanningTreeEdges = Prim.getMST(graphEdges, numberVertices); System.out.printf("The edges of the Prim MST are: \n%s\n", spanningTreeEdges); System.out.printf("The weight of the MST is %d\n", GraphUtils.totalWeight(spanningTreeEdges)); System.out.println("The edges of the graph are: \n" + graphEdges); List<WEdge> spanningTreeEdges2 = Kruskal.getMST(graphEdges, numberVertices); System.out.printf("The edges of the Kruskal MST are: \n%s\n", spanningTreeEdges2); System.out.printf("The weight of the MST is %d\n", GraphUtils.totalWeight(spanningTreeEdges2)); } }
Sample Interactionz
Here is an example run of the program with the previously given file is
The edges of the graph are: [(0, 2, 1), (1, 4, 2), (1, 6, 6), (0, 3, 6), (6, 3, 7), (6, 1, 8), (7, 4, 8), (2, 2, 7), (3, 8, 7), (2, 2, 3), (3, 1, 4), (4, 2, 8), (4, 6, 5), (5, 5, 8), (0, 7, 5)] The edges of the Prim MST are: [(0, 2, 1), (0, 3, 6), (6, 1, 8), (4, 2, 8), (3, 1, 4), (2, 2, 3), (2, 2, 7), (5, 5, 8)] The weight of the MST is 18 The edges of the graph are: [(0, 2, 1), (1, 4, 2), (1, 6, 6), (0, 3, 6), (6, 3, 7), (6, 1, 8), (7, 4, 8), (2, 2, 7), (3, 8, 7), (2, 2, 3), (3, 1, 4), (4, 2, 8), (4, 6, 5), (5, 5, 8), (0, 7, 5)] Sorted edges [(6, 1, 8), (3, 1, 4), (0, 2, 1), (2, 2, 7), (2, 2, 3), (4, 2, 8), (0, 3, 6), (6, 3, 7), (1, 4, 2), (7, 4, 8), (5, 5, 8), (1, 6, 6), (4, 6, 5), (0, 7, 5), (3, 8, 7)] Added (6, 1, 8) labels are [0, 1, 2, 3, 4, 5, 6, 7, 6] Added (3, 1, 4) labels are [0, 1, 2, 3, 3, 5, 6, 7, 6] Added (0, 2, 1) labels are [0, 0, 2, 3, 3, 5, 6, 7, 6] Added (2, 2, 7) labels are [0, 0, 2, 3, 3, 5, 6, 2, 6] Added (2, 2, 3) labels are [0, 0, 2, 2, 2, 5, 6, 2, 6] Added (4, 2, 8) labels are [0, 0, 2, 2, 2, 5, 2, 2, 2] Added (0, 3, 6) labels are [0, 0, 0, 0, 0, 5, 0, 0, 0] The edges of the Kruskal MST are: [(6, 1, 8), (3, 1, 4), (0, 2, 1), (2, 2, 7), (2, 2, 3), (4, 2, 8), (0, 3, 6), (5, 5, 8)] The weight of the MST is 18
Notice that the program opens the input file, reads it, and then builds and print a list of the edges in the graph. It then calls the Prim method to get a minimum spanning tree . The edges of the MST are then printed. Next, the Kruskal method is then called. This method displays each edge as it is added, and also displays the array showing the current labels on all vertices.