# programming language java programming environment eclipse complete the program by im 5188968

Programming Language: Java

Programming Environment: Eclipse

Complete the program by implementing the Prim’s algorithm solution. A priority queue (pq) has been included to minimize the anxiety that can be caused by this assignment. Refer to Greedy algorithms for the pseudocode for Prim’s algorithm.

The program expects one input: • Graph with the vertices.

The program should return one output: • The graph with the vertices with the MST edges added to it.

Instruction: edit the TODO part of the code only, every after the “do not edit” comment, don't edit. Make sure the code runs. Do not modify Edge.Java, Graph.Java, GraphInterface.Java, IndexMinPQ.java, Vertex.java, and the Lab5TestCase.java provided below.

**There are 6 .java files in total, you should only edit codes inside LAB5.java under the TODO part. Use comments via // or /**/ to explain the each line of the codes.**

———————————————————————————————

**// The following are Lab5.java codes, only edit the ones that are under TODO, do not touch anything else.**

**// Document the method, show each method does.**

import java.io.File;

import java.io.IOException;

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

/* Calculates the minimal spanning tree of a graph rovided below

public class LAB5 {

// TODO document this method

public static void FindMST(Graph g) {

// TODO implement this method

/*Playground:

* The following sniplets of code is provided to ease your life.

* You don't have to use it or look at it.

*/

//V: list of vertices

Vertex[] V = g.getVertices();

//E: list of edges

List E = new ArrayList();

//add implicit edges to a new list

for (Vertex u: V) {

for (Vertex v: V) {

if (u != v) {

E.add(new Edge(u, v));

}

}

}

/*

* look at my pretty edges:

Edge[] E = g.getEdges();

*/

//Init all Q[i].key = inf

double myInf = Double.POSITIVE_INFINITY;

//sample useage of a PQ:

int[] dist = {20, 30, 10, 5, 333};

IndexMinPQ Q = new IndexMinPQ(dist.length);

for (int i = 0; i

Q.insert(i, dist[i]);

}

// print each key using the iterator

System.out.println(“Priority Queue iterator example:”);

for (int i : Q) {

System.out.println(i + ” ” + dist[i]);

}

}

/********************************************

*

* You shouldn't modify anything past here

*

********************************************/

// reads in an undirected graph from a specific file formatted with one

// x/y node coordinate per line:

private static Graph InputGraph(String file1) {

Graph g = new Graph();

try (Scanner f = new Scanner(new File(file1))) {

while(f.hasNextDouble()) // each vertex listing

g.addVertex(f.nextDouble(), f.nextDouble());

} catch (IOException e) {

System.err.println(“Cannot open file ” + file1 + “. Exiting.”);

System.exit(0);

}

return g;

}

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

String file1;

System.out.printf(“Enter n”);

System.out.printf(“(e.g: points/small1 1.5)n”);

file1 = s.next();

// read in vertices

Graph g = InputGraph(file1);

g.epsilon = s.nextDouble();

FindMST(g);

s.close();

System.out.printf(“Weight of tree: %fn”, g.getTotalEdgeWeight());

}

}

————————————————————————————————

**// The following are Graph.java codes, do not edit.**

import java.util.ArrayList;

// represents a graph as a list of vertices and edges

public class Graph implements GraphInterface {

/********************************************

*

* You shouldn't modify anything past here

*

********************************************/

private ArrayList vs;

private ArrayList edges;

public double epsilon = 0; // set to maximum edge distance

private int nextVertexID = 0; // unique ID of each vertex

public Graph() {

vs = new ArrayList();

edges = new ArrayList();

}

public void addVertex(double x, double y) {

Vertex v = new Vertex();

v.x = x; v.y = y; v.ID = nextVertexID++;

vs.add(v);

}

// adds an edge to graph if it is within epsilon limit

public void addEdge(Vertex src, Vertex dst) {

if (dist(src, dst)

edges.add(new Edge(src, dst));

}

// finds the cartesian distance between two vertices

private static double dist(Vertex s, Vertex d) {

return Math.sqrt(Math.pow(s.x-d.x, 2) + Math.pow(s.y-d.y, 2));

}

public int size() {

return vs.size();

}

public Vertex[] getVertices() {

return vs.toArray(new Vertex[vs.size()]);

}

public Edge[] getEdges() {

return edges.toArray(new Edge[edges.size()]);

}

// sums up the costs of all edges in the graph

public double getTotalEdgeWeight() {

double ret = 0;

for (Edge e: edges)

ret += e.cost;

return ret;

}

}

————————————–

**// The following are GraphInterface.java codes, do not edit.**

// provides an interface for any graph

public interface GraphInterface {

void addVertex(double x, double y);

Vertex[] getVertices();

Edge[] getEdges();

double getTotalEdgeWeight();

}

————————————————–

**// The following are Edge.java codes, do not edit.**

public class Edge {

/********************************************

*

* You shouldn't modify anything past here

*

********************************************/

public Vertex src;

public Vertex dst;

public double cost;

// creates an edge between two vertices

Edge(Vertex s, Vertex d) {

src = s;

dst = d;

cost = Math.sqrt(Math.pow(s.x-d.x, 2) + Math.pow(s.y-d.y, 2));

}

}

——————————————————————–

**// The following are IndexMinPQ.java codes, do not edit.**

import java.util.Iterator;

import java.util.NoSuchElementException;

/**

* The {@code IndexMinPQ} class represents an indexed priority queue of generic keys.

* It supports the usual *insert* and *delete-the-minimum*

* operations, along with *delete* and *change-the-key*

* methods. In order to let the client refer to keys on the priority queue,

* an integer between {@code 0} and {@code maxN – 1}

* is associated with each keyâ€”the client uses this integer to specify

* which key to delete or change.

* It also supports methods for peeking at the minimum key,

* testing if the priority queue is empty, and iterating through

* the keys.

*

* This implementation uses a binary heap along with an array to associate

* keys with integers in the given range.

* The *insert*, *delete-the-minimum*, *delete*,

* *change-key*, *decrease-key*, and *increase-key*

* operations take logarithmic time.

* The *is-empty*, *size*, *min-index*, *min-key*,

* and *key-of* operations take constant time.

* Construction takes time proportional to the specified capacity.

*

* For additional documentation, see Section 2.4 of

* *Algorithms, 4th Edition* by Robert Sedgewick and Kevin Wayne.

*

* @author Robert Sedgewick

* @author Kevin Wayne

*

* @param the generic type of key on this priority queue

*/

public class IndexMinPQ> implements Iterable {

private int maxN; // maximum number of elements on PQ

private int n; // number of elements on PQ

private int[] pq; // binary heap using 1-based indexing

private int[] qp; // inverse of pq – qp[pq[i]] = pq[qp[i]] = i

private Key[] keys; // keys[i] = priority of i

/**

* Initializes an empty indexed priority queue with indices between {@code 0}

* and {@code maxN – 1}.

* @param maxN the keys on this priority queue are index from {@code 0}

* {@code maxN – 1}

* @throws IllegalArgumentException if {@code maxN

*/

public IndexMinPQ(int maxN) {

if (maxN

this.maxN = maxN;

n = 0;

keys = (Key[]) new Comparable[maxN + 1]; // make this of length maxN??

pq = new int[maxN + 1];

qp = new int[maxN + 1]; // make this of length maxN??

for (int i = 0; i

qp[i] = -1;

}

/**

* Returns true if this priority queue is empty.

*

* @return {@code true} if this priority queue is empty;

* {@code false} otherwise

*/

public boolean isEmpty() {

return n == 0;

}

/**

* Is {@code i} an index on this priority queue?

*

* @param i an index

* @return {@code true} if {@code i} is an index on this priority queue;

* {@code false} otherwise

* @throws IllegalArgumentException unless {@code 0

*/

public boolean contains(int i) {

if (i < 0 || i >= maxN) throw new IllegalArgumentException();

return qp[i] != -1;

}

/**

* Returns the number of keys on this priority queue.

*

* @return the number of keys on this priority queue

*/

public int size() {

return n;

}

/**

* Associates key with index {@code i}.

*

* @param i an index

* @param key the key to associate with index {@code i}

* @throws IllegalArgumentException unless {@code 0

* @throws IllegalArgumentException if there already is an item associated

* with index {@code i}

*/

public void insert(int i, Key key) {

if (i < 0 || i >= maxN) throw new IllegalArgumentException();

if (contains(i)) throw new IllegalArgumentException(“index is already in the priority queue”);

n++;

qp[i] = n;

pq[n] = i;

keys[i] = key;

swim(n);

}

/**

* Returns an index associated with a minimum key.

*

* @return an index associated with a minimum key

* @throws NoSuchElementException if this priority queue is empty

*/

public int minIndex() {

if (n == 0) throw new NoSuchElementException(“Priority queue underflow”);

return pq[1];

}

/**

* Returns a minimum key.

*

* @return a minimum key

* @throws NoSuchElementException if this priority queue is empty

*/

public Key minKey() {

if (n == 0) throw new NoSuchElementException(“Priority queue underflow”);

return keys[pq[1]];

}

/**

* Removes a minimum key and returns its associated index.

* @return an index associated with a minimum key

* @throws NoSuchElementException if this priority queue is empty

*/

public int delMin() {

if (n == 0) throw new NoSuchElementException(“Priority queue underflow”);

int min = pq[1];

exch(1, n–);

sink(1);

assert min == pq[n+1];

qp[min] = -1; // delete

keys[min] = null; // to help with garbage collection

pq[n+1] = -1; // not needed

return min;

}

/**

* Returns the key associated with index {@code i}.

*

* @param i the index of the key to return

* @return the key associated with index {@code i}

* @throws IllegalArgumentException unless {@code 0

* @throws NoSuchElementException no key is associated with index {@code i}

*/

public Key keyOf(int i) {

if (i < 0 || i >= maxN) throw new IllegalArgumentException();

if (!contains(i)) throw new NoSuchElementException(“index is not in the priority queue”);

else return keys[i];

}

/**

* Change the key associated with index {@code i} to the specified value.

*

* @param i the index of the key to change

* @param key change the key associated with index {@code i} to this key

* @throws IllegalArgumentException unless {@code 0

* @throws NoSuchElementException no key is associated with index {@code i}

*/

public void changeKey(int i, Key key) {

if (i < 0 || i >= maxN) throw new IllegalArgumentException();

if (!contains(i)) throw new NoSuchElementException(“index is not in the priority queue”);

keys[i] = key;

swim(qp[i]);

sink(qp[i]);

}

/**

* Change the key associated with index {@code i} to the specified value.

*

* @param i the index of the key to change

* @param key change the key associated with index {@code i} to this key

* @throws IllegalArgumentException unless {@code 0

* @deprecated Replaced by {@code changeKey(int, Key)}.

*/

@Deprecated

public void change(int i, Key key) {

changeKey(i, key);

}

/**

* Decrease the key associated with index {@code i} to the specified value.

*

* @param i the index of the key to decrease

* @param key decrease the key associated with index {@code i} to this key

* @throws IllegalArgumentException unless {@code 0

* @throws IllegalArgumentException if {@code key >= keyOf(i)}

* @throws NoSuchElementException no key is associated with index {@code i}

*/

public void decreaseKey(int i, Key key) {

if (i < 0 || i >= maxN) throw new IllegalArgumentException();

if (!contains(i)) throw new NoSuchElementException(“index is not in the priority queue”);

if (keys[i].compareTo(key)

throw new IllegalArgumentException(“Calling decreaseKey() with given argument would not strictly decrease the key”);

keys[i] = key;

swim(qp[i]);

}

/**

* Increase the key associated with index {@code i} to the specified value.

*

* @param i the index of the key to increase

* @param key increase the key associated with index {@code i} to this key

* @throws IllegalArgumentException unless {@code 0

* @throws IllegalArgumentException if {@code key

* @throws NoSuchElementException no key is associated with index {@code i}

*/

public void increaseKey(int i, Key key) {

if (i < 0 || i >= maxN) throw new IllegalArgumentException();

if (!contains(i)) throw new NoSuchElementException(“index is not in the priority queue”);

if (keys[i].compareTo(key) >= 0)

throw new IllegalArgumentException(“Calling increaseKey() with given argument would not strictly increase the key”);

keys[i] = key;

sink(qp[i]);

}

/**

* Remove the key associated with index {@code i}.

*

* @param i the index of the key to remove

* @throws IllegalArgumentException unless {@code 0

* @throws NoSuchElementException no key is associated with index {@code i}

*/

public void delete(int i) {

if (i < 0 || i >= maxN) throw new IllegalArgumentException();

if (!contains(i)) throw new NoSuchElementException(“index is not in the priority queue”);

int index = qp[i];

exch(index, n–);

swim(index);

sink(index);

keys[i] = null;

qp[i] = -1;

}

/***************************************************************************

* General helper functions.

***************************************************************************/

private boolean greater(int i, int j) {

return keys[pq[i]].compareTo(keys[pq[j]]) > 0;

}

private void exch(int i, int j) {

int swap = pq[i];

pq[i] = pq[j];

pq[j] = swap;

qp[pq[i]] = i;

qp[pq[j]] = j;

}

/***************************************************************************

* Heap helper functions.

***************************************************************************/

private void swim(int k) {

while (k > 1 && greater(k/2, k)) {

exch(k, k/2);

k = k/2;

}

}

private void sink(int k) {

while (2*k

int j = 2*k;

if (j

if (!greater(k, j)) break;

exch(k, j);

k = j;

}

}

/***************************************************************************

* Iterators.

***************************************************************************/

/**

* Returns an iterator that iterates over the keys on the

* priority queue in ascending order.

* The iterator doesn't implement {@code remove()} since it's optional.

*

* @return an iterator that iterates over the keys in ascending order

*/

public Iterator iterator() { return new HeapIterator(); }

private class HeapIterator implements Iterator {

// create a new pq

private IndexMinPQ copy;

// add all elements to copy of heap

// takes linear time since already in heap order so no keys move

public HeapIterator() {

copy = new IndexMinPQ(pq.length – 1);

for (int i = 1; i

copy.insert(pq[i], keys[pq[i]]);

}

public boolean hasNext() { return !copy.isEmpty(); }

public void remove() { throw new UnsupportedOperationException(); }

public Integer next() {

if (!hasNext()) throw new NoSuchElementException();

return copy.delMin();

}

}

/**

* Unit tests the {@code IndexMinPQ} data type.

*

* @param args the command-line arguments

*/

/*

public static void main(String[] args) {

// insert a bunch of strings

String[] strings = { “it”, “was”, “the”, “best”, “of”, “times”, “it”, “was”, “the”, “worst” };

IndexMinPQ pq = new IndexMinPQ(strings.length);

for (int i = 0; i

pq.insert(i, strings[i]);

}

// delete and print each key

while (!pq.isEmpty()) {

int i = pq.delMin();

StdOut.println(i + ” ” + strings[i]);

}

StdOut.println();

// reinsert the same strings

for (int i = 0; i

pq.insert(i, strings[i]);

}

// print each key using the iterator

for (int i : pq) {

StdOut.println(i + ” ” + strings[i]);

}

while (!pq.isEmpty()) {

pq.delMin();

}

}

*/

}

——————————————————-

**// The following are Vertex.java codes, do not edit. **

// represents a vertex in a graph, including a unique ID to keep track of vertex

public class Vertex {

/********************************************

*

* You shouldn't modify anything past here

*

********************************************/

public double x;

public double y;

public int ID;

}

——————————–