Java Program

Selects a text file from your computer using either a Java Swing JFileChooser or a JavaFX FileChooser, which starts out showing the files in the same directory from which the program was executed.

Reads the selected text file. The text file will form an adjacency matrix representation of a graph.

Given a file where the value of each node is an integer (in the range Integer.MIN_VALUE through Integer.MAX_VALUE, inclusive, create a Min-Heap containing the nodes of the graph, as follows: (see example below)

Read the node on the first line, create a 1-node heap, output the mnemonic of the node in the Heap and its index in the array holding the Heap.

Read the node on the second line, add it to the existing heap, and output the mnemonics of the nodes in the Heap on one line and the indices of the elements of the Heap, comma separated.

Continue in this manner until you have created a Min-Heap containing all the nodes in the input file.

You may assume that all input files have integral values (you need not check for this).In case of identical values, assume that the node whose name comes first in a lexical ordering has the minimum value

Implement the following methods for the heap

i. build-heap()

ii. heapify(..)

iii. heapsort(...)

iv . heap-extract-min(..)

v . heap-insert(..)

vi. left(..)

vii. parent()

viii. right()

Output a minimum spanning tree for the graph using Prims Algorithm, then output the total length of the MST

In your implementation of Prims Algorithm, use your heap to store the priority min-queue used to select the next edge to add to the MST.

Begin from the node that is the first node you read in the input file.

Output the edges in the MST, in the order added, to a file, to the console, or both.

For this program, the nodes in the graph need not have a value, and if they have a value, it need not be an int.

You may assume that all input files have integral values for the edges (you need not check for this). In case of identical edge values, you may resolve the ambiguity any way that you want to. In fact, each file will be symmetrical around the main diagonal. (Its the equivalent to an undirected graph.)

Example of an input file;

~ val a b c d e f g

A 4 ~ 1 9 2 ~ ~ ~

B 6 1 ~ ~ 4 8 ~ ~

C 6 9 ~ ~ 4 ~ 3 ~

D 10 2 4 4 ~ 3 4 5

E 5 ~ 8 ~ 3 ~ ~ 6

F 7 ~ ~ 3 4 ~ ~ 2

G 2 ~ ~ ~ 5 6 2 ~

Output:

MST Edges, in order of addition: ab, ad, de, cd, cf, fg

MST length: 15

Note: The MST may not be unique, and any of the correct answers are OK. For instance, another correct answer (with MST length still 16) would be: ab, ad, de, df, fg, cf