look at the content of the skeleton file Vertex.java. There you will find only 1 method you need to implement:

• Vertex (name): This constructor creates a new vertex by just assigning it the name 'name' and creating a new instance of the adjacency list.

Please, look at the content of the skeleton file Edge.java. There you will find only 1 method you need to implement:

• Edge(from, to, weight): This constructor creates a new edge by assigning it an origin vertex (from), a destination vertex (to) and a weight.

Finally, please look at the content of the skeleton file Graph.java. You can see there are 9 methods you must implement in the .cpp file:

• Graph( ): This constructor creates a new object vlist (allocates memory to it).

• addVertex(v): This method creates a new vertex (using the constructor Vertex) named 'v' and appends it to the list of vertices (vlist).

• getVertex(v): This methods performs a linear search on vlist. If an element with a name equal to 'v' is found, the element (a vertex) is returned. If no vertex with name equal to 'v' is found in the list, NULL is returned.

• addEdge(v1, v2, weight): This method uses the method getVertex() to obtain the vertices identified by the names v1 and v2. Next, it uses the constructor Edge to create the new edge and adds it to the corresponding adjacency list. If vertices v1 and v2 are different, a second edge originating at v2 and ending at v1 must be added as well.

• getEdge(v1,v2): This method uses the method getVertex() to obtain the vertices identified by the names v1 and v2. Next, it performs a linear search on the corresponding adjacency list to check whether the edge exists. If so, it returns it. Otherwise, it returns NULL

• MST(): This method returns a graph, corresponding to the minimum spanning tree of the original graph. You can use Prim or Kruskal algorithms to solve this problem. Bear in mind that Kruskal requires you to implement a disjoint-set data structure as well.

• MSTCost(): This method returns the cost of the minimum spanning tree

• SP(v1,v2): This method returns a graph containing the route (sequence of vertices) of the shortest path from v1 to v2

• SPCost(v1,v2): This method returns the cost of the shortest path between v1 and v2

Vertex.java

import java.util.ArrayList; public class Vertex { public String name; public ArrayList adjlist; public Vertex(String _name) { } } 

Graph.java

import java.util.ArrayList; public class Graph { public ArrayList vlist; public Graph() { } public void addVertex(String name) { } public Vertex getVertex(String name) { return null; } public void addEdge(String from, String to, int weight) { } public Edge getEdge(String from, String to) { return null; } public int MSTCost() { return -1; } public Graph MST() { return null; } public int SPCost(String from, String to) { return 0; } public Graph SP(String from, String to) { return null; } } 

Edge.java

public class Edge { public Vertex from, to; public int weight; public Edge(Vertex _from, Vertex _to, int _weight) { } }