JAVA help thank you!

The file UDGraph.java contains code for a class UDGraph, an unweighted directed graph represented by a boolean adjacency matrix adjMatrix[][]. For simplicity, vertices are denoted by ints in the range 0...n - 1, where n is the number of vertices. Each entry adjMatrix[i][j] is true if (i, j) is an edge of the graph; false otherwise.

The UDGraph class currently has the following methods.

UDGraph(int n) Constructs a new UDGraph with n vertices and no edges. getNumVertices() Returns the number of vertices in the UDGraph. getNumEdges() Returns the number of edges in the UDGraph. validVertex(int v) True if v is a valid vertex number (0...n - 1). hasEdge(int o, int d) True if the graph contains edge (o, d). addEdge(int o, int d) Adds edge (o, d) to the graph (if not already there). removeEdge(int o, int d) Removes edge (o, d) from the graph (if there). toString() Returns a String representation of the UDGraph.

You are welcome to use these methods and/or manipulate the fields "adjMatrix", "vertices", and "edges" directly, as you prefer. The addEdge and removeEdge methods have the advantage that they update the "edges" count correctly (always checking whether the edge is present in the graph before the update).

Part I: Finding vertices reachable by length-2 paths ---------------------------------------------------------------- Fill in the body of the method UDGraph.length2Paths(). This method constructs and returns a UDGraph with the same number of vertices as "this" UDGraph. The new graph contains the edge (v, w) if and only if there is a path of length 2 from v to w in "this" graph--in other words, there is some vertex u such that (v, u) and (u, w) are both edges of "this" graph.

Note that a length-2 path can start and end at the same vertex: if "this" graph contains the edges (v, w) and (w, v), then it contains a length-2 path from v to itself, and the new graph should contain the self-edge (v, v). Moreover, if "this" graph contains the self-edge (v, v), then is a length-2 path, so the new graph should contain (v, v).

If a vertex w can be reached from a vertex v by a length-1 path (one edge) in "this" graph but _not_ by a length-2 path, the new graph should _not_ contain (v, w).

Try to think of the fastest, simplest code for length2Paths(). It's possible to do it with a relatively simple triply-nested loop. You will have to explain your algorithm to your TA. If your TA thinks your algorithm is too slow, you'll be asked to do it again.

Your solution should not change "this" graph.

Part II: Finding vertices reachable by length-k paths ---------------------------------------------------------------- Fill in the body of the method UDGraph.paths(int length). This method creates and returns a UDGraph with the same number of vertices as "this" UDGraph. The new graph contains the edge (v, w) if and only if there is a path of length "length" (the parameter) from v to w in "this" graph. Your method should work for any "length" of 2 or greater.

Note that a length-k path is permitted to use an edge multiple times. For example, is a valid length-5 path.

Hint: First calculate all the paths of length (k - 1). Once you know these, it's straightforward to compute all the paths of length k in a manner similar to what you did for Part I.

There is test code in UDGraph.main() for both Parts I and II.

Check-off --------- Show your TA your code for length2Paths() and explain how you did it. Run the test code to show that length2Paths() works. Run the test code to show that paths() works.

/* UDGraph.java */

import java.io.*;

import java.util.*;

/**

* The UDGraph class represents an unweighted directed graph.

* Implemented with an adjacency matrix.

*/

public class UDGraph

{

/**

* adjMatrix references the adjacency matrix of the graph.

* vertices is the number of vertices in the graph.

* edges is the number of edges in the graph.

*

* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.

*/

private boolean[][] adjMatrix;

private int vertices;

private int edges;

/**

* Constructs a graph with n vertices and no edges.

*/

public UDGraph(int n) {

vertices = n;

edges = 0;

adjMatrix = new boolean[n][n];

for (int i = 0; i < vertices; i++ ) {

for (int j = 0; j < vertices; j++ ) {

adjMatrix[i][j] = false;

}

}

}

/**

* Returns the number of vertices.

* @return this graph's vertex count.

*/

public int getNumVertices() {

return vertices;

}

/**

* Returns the number of edges.

* @return this graph's edge count.

*/

public int getNumEdges() {

return edges;

}

/**

* Returns true if v is a valid vertex number; false otherwise.

* @param v the vertex.

* @return boolean indicating existence of vertex number v.

*/

public boolean validVertex(int v) {

return (v >= 0) && (v < vertices);

}

/**

* Returns true if edge (origin, destination) exists; false otherwise.

* @param origin the origin vertex.

* @param destination the destination vertex.

* @return boolean indicating the presence of edge (origin, destination).

*/

public boolean hasEdge(int origin, int destination) {

if (validVertex(origin) && validVertex(destination)) {

return adjMatrix[origin][destination];

} else {

return false;

}

}

/**

* Creates the edge (origin, destination). If the edge did not already

* exists, increments the edge count.

* @param origin the origin vertex.

* @param edstination the destination vertex.

*/

public void addEdge(int origin, int destination) {

if (validVertex(origin) && validVertex(destination)) {

if (!adjMatrix[origin][destination]) {

adjMatrix[origin][destination] = true;

edges++;

}

}

}

/**

* Deletes the edge (origin, destination). If the edge existed, decrements

* the edge count.

* @param origin the origin vertex.

* @param destination the destination vertex.

*/

public void removeEdge(int origin, int destination) {

if (validVertex(origin) && validVertex(destination)) {

if (adjMatrix[origin][destination]) {

adjMatrix[origin][destination] = false;

edges--;

}

}

}

/**

* Returns a new UDGraph with the same vertices as "this" UDGraph.

* The new graph has an edge (v, w) if and only if there is a path of

* length 2 from v to w in "this" graph.

* *** DO NOT CHANGE "this" GRAPH!!! ***

* @return the new UDGraph.

*/

public UDGraph length2Paths() {

UDGraph newGraph = new UDGraph(vertices);

// Put your answer to Part I here.

return newGraph;

}

/**

* Returns a new UDGraph with the same vertices as "this" UDGraph.

* The new graph has an edge (v, w) if and only if there is a path of

* length "length" from v to w in "this" graph.

* @param length the length of paths used to construct the new graph.

* @return the new UDGraph.

*/

public UDGraph paths(int length) {

UDGraph newGraph = new UDGraph(vertices);

// Put your answer to Part II here.

return newGraph;

}

/**

* Returns a String representing the adjacency matrix, including the number

* of vertices and edges.

* @return a String representing the adjacency matrix.

*/

public String toString() {

int i, j;

String s = vertices + " vertices and " + edges + " edges ";

for (i = 0; i < vertices; i++) {

for (j = 0; j < vertices - 1; j++) {

s = s + (adjMatrix[i][j] ? "t" : ".") + " ";

}

s = s + (adjMatrix[i][j] ? "t" : ".") + " ";

}

return s;

}

public static void main(String[] args) {

System.out.println(" *** Square the unweighted directed graph! *** ");

// Create an 11-vertex graph.

System.out.println("Creating a graph with 11 vertices");

UDGraph graph = new UDGraph(11);

graph.addEdge(0, 8);

graph.addEdge(1, 0);

graph.addEdge(1, 3);

graph.addEdge(2, 0);

graph.addEdge(3, 2);

graph.addEdge(3, 5);

graph.addEdge(4, 2);

graph.addEdge(4, 5);

graph.addEdge(5, 7);

graph.addEdge(5, 9);

graph.addEdge(6, 4);

graph.addEdge(6, 7);

graph.addEdge(8, 4);

graph.addEdge(8, 6);

graph.addEdge(8, 10);

graph.addEdge(9, 1);

graph.addEdge(10, 6);

boolean goodJob = true;

String t1String = "11 vertices and 17 edges . . . . . . . . t . . " +

"t . . t . . . . . . . t . . . . . . . . . . . . t . . t . . . . . " +

". . t . . t . . . . . . . . . . . . t . t . . . . . t . . t . . . " +

". . . . . . . . . . . . . . . t . t . . . t . t . . . . . . . . . " +

". . . . . . t . . . . ";

System.out.println(" The original graph is " + graph);

if (!t1String.equals(graph.toString())) {

System.out.println("Error: the original graph should be " +

t1String);

goodJob = false;

}

// Do length-2 paths work?

String t2String = "11 vertices and 25 edges . . . . t . t . . . t " +

". . t . . t . . t . . . . . . . . . . t . . t . . . . . . t . t . " +

"t . . . . . . t . t . . t . . . . . . . . . . . t . . t . . . . . " +

". . . . . . . . . . . . . t . t t t t . . . t . . t . . . . . . . " +

". . . . t . . t . . . ";

System.out.println("Testing length-2 paths.");

System.out.println("The graph of length-2 paths is " +

graph.length2Paths());

if (!t2String.equals(graph.length2Paths().toString())) {

System.out.println("Error: the length-2 path graph should be " +

t2String);

goodJob = false;

}

// Do length-3 paths work?

String t3String = "11 vertices and 34 edges . . t . t t t t . . . " +

"t . . . t . t t . t t . . . . t . t . . . t . t . . . . . . t . . " +

". t . . . . . . t . . t . . t . . . . . . . t . . . . . . t . t . " +

". . . . . . . . . . . t . t . t t . t . t . . . t . . t . . t . . " +

". . t . . t . . . . . ";

System.out.println("Testing length-3 paths.");

System.out.println("The graph of length-3 paths is " +

graph.paths(3));

if (!t3String.equals(graph.paths(3).toString())) {

System.out.println("Error: the length-3 path graph should be " +

t3String);

goodJob = false;

}

// Do length-4 paths work?

String t4String = "11 vertices and 49 edges t . t . t t . t . t . " +

". t t . t t t t t . . . . t . t t t t . . . t . . t t . t . . . t " +

"t . . t t . t . . . t . . t . . t . . t . . . t . . . . . . t . . " +

". . . . . . . . . . . t t t . . t . t t t . t . . . t . t t . t t " +

"t . . . . . . t . t . ";

System.out.println("Testing length-4 paths.");

System.out.println("The graph of length-4 paths is " +

graph.paths(4));

if (!t4String.equals(graph.paths(4).toString())) {

System.out.println("Error: the length-4 path graph should be " +

t4String);

goodJob = false;

}

// Do length-5 paths work?

String t5String = "11 vertices and 63 edges t t t . . t . t t t . " +

"t . t t t t t t . t t t . t . t t . t . t . . . t . t t t t t . . " +

". . t . t t t t t . . t . . . t . t t . t t t . . t t . t . . . t " +

". . . . . . . . . . . t t . t t . t t t t t . t t . t t t t t . . " +

". t . . . . . . t . . ";

System.out.println("Testing length-5 paths.");

System.out.println("The graph of length-5 paths is " +

graph.paths(5));

if (!t5String.equals(graph.paths(5).toString())) {

System.out.println("Error: the length-5 path graph should be " +

t5String);

goodJob = false;

}

if (goodJob) {

System.out.println(" *** Good Job! *** ");

}

}

}