Create a JUnit test file for the AMGraph class, even though it is not implemented yet. For each step below, start each test case with something like this, using Strings as the data:

AMGraph instance = new AMGraph();

instance.addVertex(Clara);

Start with writing test cases for the easy methods: (isEmpty, size). The size method for a graph should return the number of vertices (not the number of edges).

Write a test for the addVertex method next. For the addVertex test, you need to think about the state variable that is maintained (numVertices) and ensure that it changes appropriately as elements are added. You also want to look at the matrix that can be printed out by the toString() method, and make sure your vertex is showing up in the matrix.

Write a test for the removeVertex method next. Again, test the size, and look at the matrix representation.

Now write a test for the addEdge method. Add vertices in the test case method so that your graph looks like this:

For the removeEdge test, you should check that the matrix is revised correctly if you remove the edge that connects A and D.

You dont need to write a test case for the toSring() traversals or isConnected methods.

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

package DataStructures;

import ADTs.GraphADT; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.logging.*;

public class AMGraph implements GraphADT {

private int numVertices; private final int DEFAULT_CAPACITY = 5; private boolean[][] matrix; private T[] vertices;

/** * Constructor */ public AMGraph() { numVertices = 0; this.vertices = (T[])(new Object[DEFAULT_CAPACITY]); this.matrix = new boolean[DEFAULT_CAPACITY][DEFAULT_CAPACITY]; } /** * Adds the (generic) vertex to the graph * @param vertex the vertex to be added */ @Override public void addVertex(T vertex) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. // TODO: // check if space, if not, expandCapacity // add to array // set all links in the matrix for this vertex to false // increment }

/** * Removes the specified vertex * @param vertex the vertex to be removed */ @Override public void removeVertex(T vertex) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. }

/** * Adds an edge between the two specified vertices * @param vertex1 the first vertex * @param vertex2 the second vertex */ @Override public void addEdge(T vertex1, T vertex2) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. //TODO: add this code (look at removeEdge()) }

/** * Removes the edge between the two specified vertices * @param vertex1 the first vertex * @param vertex2 the second vertex */ @Override public void removeEdge(T vertex1, T vertex2) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. }

/** * Returns an ArrayList of T vertices arrived at through * depth-first traversal starting at specified vertex * @param startVertex * @return array of vertices from depth-first traversal */ @Override public ArrayList depthFirstTraversal(T startVertex) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. // IGNORE this for Lab 13, we will not implement this }

/** * Returns an ArrayList of T vertices arrived at through * breadth-first traversal starting at specified vertex * @param startVertex * @return array of vertices from breadth-first traversal */ @Override public ArrayList breadthFirstTraversal(T startVertex) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. }

/** * Returns true if this graph is connected, false otherwise * @return true if this graph is connected */ @Override public boolean isConnected() { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. //TODO // for every vertex, run a breadth first search // if every one of them returns a results list that contains // all the other nodes (size of list is the same as numVertices) // then the graph is connected }

@Override public boolean isEmpty() { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. //TODO }

@Override public int size() { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. //TODO }

@Override public String toString() { String m = "\t\t\t"; for (int i = 0; i < numVertices; i++) { m = m.concat(vertices[i].toString() + "\t"); } m = m.concat(" "); for (int i = 0; i < numVertices; i++) { m = m.concat("\t " + vertices[i].toString() + "\t"); for (int j = 0; j < numVertices; j++) { m = m.concat("\t" + matrix[i][j]); } m = m.concat(" "); } return "AMGraph{" + "numVertices=" + numVertices + ", matrix: " + m + "}"; }

private void expandCapacity() { T[] largerVertices = (T[])(new Object[vertices.length*2]); boolean[][] largerMatrix = new boolean[vertices.length*2][vertices.length*2]; for (int i = 0; i < numVertices; i++) { for (int j = 0; j < numVertices; j++) { largerMatrix[i][j] = matrix[i][j]; } largerVertices[i] = vertices[i]; } vertices = largerVertices; matrix = largerMatrix; }

private int getIndex(T vertex1) { throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates. //TODO: // loop through the vertices, see if the vertex is equal to the one // passed in. Think about what equality means. Do you want to // use == or do you want to use .equals()? // if you find a vertex that matches the one passed in, return its index }

private boolean indexIsValid(int index1) { if ((index1 == -1) || (index1 >= numVertices)) { return false; } return true; } }

-------

package ADTs;

import java.util.ArrayList;

public interface GraphADT extends CollectionADT { /** * * Adds the vertex to the graph * @param vertex the vertex to be added */ public void addVertex(T vertex) ; /** * Removes the specified vertex * @param vertex the vertex to be removed */ public void removeVertex(T vertex);

/** * Adds an edge between the two specified vertices * @param vertex1 the first vertex * @param vertex2 the second vertex */ public void addEdge(T vertex1, T vertex2); /** * Removes the edge between the two specified vertices * @param vertex1 the first vertex * @param vertex2 the second vertex */ public void removeEdge(T vertex1, T vertex2); /** * Returns an ArrayList of T vertices arrived at through * depth-first traversal starting at specified vertex * @param startVertex * @return array of vertices from depth-first traversal */ public ArrayList depthFirstTraversal(T startVertex); /** * Returns an ArrayList of T vertices arrived at through * breadth-first traversal starting at specified vertex * @param startVertex * @return array of vertices from breadth-first traversal */ public ArrayList breadthFirstTraversal(T startVertex); /** * Returns true if this graph is connected, false otherwise * @return true if this graph is connected */ public boolean isConnected(); }