Hi, with the given code, how do I write out the entire method of kruskalMST?

--------------------------------

import java.io.*; import java.util.*; import java.util.concurrent.atomic.AtomicInteger; import java.util.function.Function; import java.util.Comparator; import java.util.PriorityQueue;

public class GraphDemo { public static final Double INFINITY = Double.MAX_VALUE;

public static void main(String []args) throws GraphException { if (args.length != 1) { System.out.println("Usage: GraphDemo "); System.exit(1); } City c1, c2; Scanner console; int menuReturnValue, i,j; Function f = aCity -> System.out.printf("%-2d %-30s%n",aCity.getKey(),aCity.getLabel().trim()); Graph g = readGraph(args[0]); long s = g.size(); menuReturnValue = -1; while (menuReturnValue != 0) { menuReturnValue = menu(); switch(menuReturnValue) { case 1: //Incidence Matrix System.out.println(); System.out.println("Incidence Matrix For The Undirected Graph In "+args[0]); System.out.println(); //Add code here to generate the incidence matrix of the graph long [][]incidenceMat = new long [(int) s][(int) g.countEdges()]; int column = 0; for (i = 0; i < s; i++) { for (j = 0; j < s; j++){ if (g.isEdge(g.retrieveVertex(new City(i + 1)), g.retrieveVertex(new City(j + 1)))){ incidenceMat[i][column] = 1; incidenceMat[j][column] = 1; column++; } } } //mat being generated for (i = 0; i Gonzales 10.20 mi //Gonzales -> Metaire 32.00 mi //Metaire -> New Orleans 7.25 mi dijkstra(g, dist, pred, i, j); Deque predStack = new ArrayDeque(); for(int k = j-1; pred[k] != -1; k = pred[k]) { predStack.push(k); } predStack.push(i-1); int n = predStack.size(); for(int m = 1; m < n; m++) { Integer p = predStack.getFirst(); predStack.pop(); System.out.printf("%s \t->\t %-15s\t%.2f mi %n",((g.retrieveVertex(new City(p+1)).getLabel())), ((g.retrieveVertex(new City(predStack.getFirst())).getLabel())), g.retrieveEdge( g.retrieveVertex( new City (p+1)), g.retrieveVertex (new City(predStack.getFirst()+1)))); //System.out.printf("%-12.2s -> %-12.2s %12.2s mi", ((g.retrieveVertex(new City(q+1)).getLabel()))); //System.out.printf("%-12.2s -> %12.2s %12.2s mi",g.retrieveEdge( g.retrieveVertex( new City (p+1)), g.retrieveVertex (new City(q+1)))); } //End code System.out.println("========================================================================================="); System.out.printf("Total distance: %f miles.%n%n",dist[j-1]); //changed dist[dest-1] to dist[j-1] due to error } else System.out.printf("There is no path.%n%n"); break; case 4: //post-order depth-first-search traversal System.out.println(); System.out.println("PostOrder DFS Traversal For The Graph In "+args[0]); System.out.println("=========================================================================="); //Add code here to invoke the dfsTraverse method using the function defined above g.dfsTraverse(f); System.out.println("=========================================================================="); System.out.println(); System.out.println(); break; case 5: //breadth-first-search traversal System.out.println(); System.out.println("BFS Traversal For The Graph In "+args[0]); System.out.println("=========================================================================="); //Add code here to invoke the bfsTraverse method using the function defined above g.bfsTraverse(f); //code ends here System.out.println("=========================================================================="); System.out.println(); System.out.println(); break; case 6: //number of edges System.out.println(); System.out.println("The graph has "+g.countEdges()+"."); System.out.println(); break; case 7: //topoSort (project 4) System.out.println(); System.out.println("Topological Sorting of The Graph In "+args[0]); System.out.println("=========================================================================="); int[] top = new int[(int)g.size()]; topoSort(g,top); for (i=1; i<=g.size(); i++) { c1 = g.retrieveVertex(new City(top[i-1])); f.apply(c1); } System.out.println("=========================================================================="); System.out.printf("%n%n"); break; case 8: //kruskalMST (project 4) int[] mstK = new int[(int)g.size()]; double totalWt = kruskalMST(g,mstK); String cityNameA,cityNameB; for (i=1; i<=g.size(); i++) { if (mstK[i-1] == -1) cityNameA = "NONE"; else cityNameA = g.retrieveVertex(new City(mstK[i-1])).getLabel().trim(); cityNameB = g.retrieveVertex(new City(i)).getLabel().trim(); System.out.printf("%d-%s parent[%d] <- %d (%s)%n",i,cityNameB,i,mstK[i-1],cityNameA); } System.out.printf("The weight of the minimum spanning tree/forest is %.2f miles.%n%n",totalWt); break; default: ; } //end switch }//end while }//end main

/** * This method reads a text file formatted as described in the project description. * @param filename the name of the DIMACS formatted graph file. * @return an instance of a graph. */ private static Graph readGraph(String filename) { try { Graph newGraph = new Graph(); try (FileReader reader = new FileReader(filename)) { char temp; City c1, c2, aCity; String tmp; int k, m, v1, v2, j, size=0, nEdges=0; Integer key, v1Key,v2Key; Double weight; Scanner in = new Scanner(reader); while (in.hasNext()) { tmp = in.next(); temp = tmp.charAt(0); if (temp == 'p') { size = in.nextInt(); nEdges = in.nextInt(); } else if (temp == 'c') { in.nextLine(); } else if (temp == 'n') { key = in.nextInt(); tmp = in.nextLine(); aCity = new City(key,tmp); newGraph.insertVertex(aCity); } else if (temp == 'e') { v1Key = in.nextInt(); v2Key = in.nextInt(); weight = in.nextDouble(); c1 = new City(v1Key); c2 = new City(v2Key); newGraph.insertEdge(c1,c2,weight); } } } return newGraph; } catch(IOException exception) { System.out.println("Error processing file: "+exception); } return null; }

/** * Display the menu interface for the application. * @return the menu option selected. */ private static int menu() { Scanner console = new Scanner(System.in); int option; do { System.out.println(" BASIC WEIGHTED GRAPH APPLICATION "); System.out.println("====================================="); System.out.println("[1] Incidence Matrix (undirected)"); System.out.println("[2] Transitive Matrix"); System.out.println("[3] Single-source Shortest Path"); System.out.println("[4] Postorder DFS Traversal"); System.out.println("[5] BFS Traversal"); System.out.println("[6] Number of Edges"); System.out.println("[7] Topological Sort Labeling"); System.out.println("[8] Kruskal's Minimal Spanning Tree"); System.out.println("[0] Quit"); System.out.println("====================================="); System.out.printf("Select an option: "); option = console.nextInt(); if (option < 0 || option > 8) { System.out.println("Invalid option...Try again"); System.out.println(); } else return option; }while(true); } /** * an auxiliary method for the topoSort method. * @param g a weighted directed graph * @param v current vertex * @param seen a 1-D boolean matrix of vertices that * have been marked. * @param linearOrder a 1-D array containing the * topologically sorted list. * @param index current index. */ private static void dfsOut(Graph g, int v, boolean seen[], int linearOrder[],AtomicInteger index) throws GraphException { //implement this method (project 4) seen[v - 1] = true; for (int i = 1; 1 <= (int)g.size(); i++) { if (g.isEdge(new City(v), new City(i)) && !seen[i - 1]) dfsOut(g, i, seen, linearOrder, index); } linearOrder[index.get()] = v; index.decrementAndGet(); } /** * This method generates a listing of the vertices of a weighted * directed graph using the reverse dfs topological sorting. * @param g a weighted directed graph * @param linearOrder an array in which the topologically sorted * list is stored. */ private static void topoSort(Graph g, int linearOrder[]) throws GraphException { // //implement this method (project 4) int z = (int) g.size(); AtomicInteger index = new AtomicInteger((int) g.size() -1); boolean seen[] = new boolean[z]; for (int i =0; i

/** * auxilliary data structure to store the information * about an edge for the MST algorithm * */ private static class EdgeType implements Comparable { /** * compares edge using weight as the primary key, * source vertex as the secondary key and destination * vertex as the tertiary key * @param another a reference to an edge * @return -1 when this edge comes before the specified * edge, 0 if the edges are identical, otherwise 1 */ public int compareTo(EdgeType another) { if (weight < another.weight) return -1; if (weight > another.weight) return 1; if (source < another.source) return -1; if (source > another.source) return 1; if (destination < another.destination) return -1; if (destination > another.destination) return 1; return 0; } public double weight; public int source; public int destination; public boolean chosen; }

/** * Find the root vertex of the tree in which the specified vertex is; * for use in Kruskal's algorithm * @param parent the parent implementation of a subtree of a graph * @param v a vertex * @return the root of this subtree */ private static int find(int[] parent, int v) { // //implement this method (project 4) while (parent[v] != -1) v = parent[v]; return v; } /** * This method generates a minimum spanning tree using Kruskal's * algorithm. If no such MST exists, then it generates a minimum spanning forest. * @param g a weighted directed graph * @param parent the parent implementation of the minimum spanning tree/forest * @return the weight of such a tree or forest. * @throws GraphException when this graph is empty *

 * {@code * If a minimum spanning tree cannot be generated, * the parent implementation of a minimum spanning tree or forest is * determined. This implementation is based on the union-find stragey. * } * 

*/ private static double kruskalMST(Graph g, int [] parent) throws GraphException { // //implement this method (project 4) PriorityQueue k = new PriorityQueue(); for(int i = 1; i < g.size(); i++){ City c1 = g.retrieveVertex(new City(i)); for(int b =1; b < g.size(); b++){ City c2 = g.retrieveVertex(new City(b)); if(g.isEdge(c1, c2)){ EdgeType et = new EdgeType(); et.source = i; et.destination = b; et.weight = g.retrieveEdge(c1, c2); k.add(et); } } } } /** * This method computes the cost and path arrays using the * Dijkstra's single-source shortest path greedy algorithm. * @param g an instance of a weighted directed graph * @param dist an array containing shortest distances from a source vertex * @param pred an array containing predecessor vertices along the shortest path * @throws GraphException on call to retrieveEdge on non-existent edge */ private static void dijkstra(Graph g, double[] dist, int[] pred, int source, int destination) throws GraphException { int s = (int) g.size(); boolean seen[] = new boolean[s]; int numSeen=0; for(int i = 0; i < s; i++) { dist[i] = INFINITY; pred[i] = -1; seen[i] = false; }

dist[source-1] = 0;

while(numSeen < s) { double k = INFINITY; int u = -1; for (int i = 0; i < g.size(); i++) { if(dist[i] < k && seen[i]==false){ u = i; k = dist[i]; }

}

if(u == destination-1 || u==- 1||k == INFINITY){

return; }

seen[u]= true; numSeen++;

for (int i = 0; i < g.size(); i++) {

if(g.isEdge(g.retrieveVertex(new City(u+1)), g.retrieveVertex(new City(i+1)))){

double weight = g.retrieveEdge(g.retrieveVertex(new City(u+1)), g.retrieveVertex(new City(i+1))); double lengthv = dist[u]+ weight;

if(lengthv < dist[i]){

dist[i]= lengthv; pred[i]= u; } }

} }

} /* //Implement this method int numSeen = 0; long s = g.size(); double length =0; boolean[] seen = new boolean[(int) s]; for(int i =0; i

double weight = g.retrieveEdge(g.retrieveVertex(new City(u+1)), g.retrieveVertex(new City(i+1))); double lengthv = dist[u]+ weight; if(lengthv < dist[i]) { dist[i] = lengthv; pred[i] = u; } } } } */ }