/*

* Return the number of edges in the graph.

*

* You MAY NOT use the size method of the LinkedList class

* (Hint: LinkedList is Iterable, so iterate through each list)

*/

public int E() {

// TODO1: fix this *** see the restrictions above!

return -1;

}

/*

* adj

*

* Return the list of neighbors of vertex v as an Iterable.

* @throws java.lang.IndexOutOfBoundsException for an invalid vertex

*

* You MAY NOT return a reference to the actual LinkedList instance

* Hint: create some type of Iterable and populate it with the contents of

* the corresponding list

*/

public Iterable adj(int v) {

// TODO2 fix/implement this method

if (v < 0 || v >= this.V()) throw new IndexOutOfBoundsException();

return null;

// here is the alternate approach discussed in overview video

// return aloll.get(v); this would return a reference to the actual list, which could then

// allow the recipient to alter the graph :(

}

/* deleteVertex

*

* MUST:

* remove vertex v if it exists

* remove all edges involving vertex v

*

* compress the arrayList by moving the last vertex to the deleted vertex array location

* NOTE: this means updating all the references to that vertex in the rest of the data structure

*

* Example: delete vertex 4 in a graph of size 10. (vertices are 0,1,...,9 )

* After deleting vertex 4 and all its edges, move vertex 9's list to

* the now unused array location 4

* effectively replacing the old vertex 4 with that vertex.

* any edge involving 9 should now refer to 4

*

* Hint: first remove the old (9s), then add the (4)

*

* returns:

* true if successful

* false if v was invalid

*/

public boolean deleteVertex(int v) {

//TODO3 implement this method

return false;

}

public class GraphPP { // Graph++ - incrementally better than the old Graph

// V, E instance variables are not here!

private ArrayList> aloll; //an adjacency list stored in an ArrayListOfLinkedLists

/**

* Create an empty graph with V vertices.

*/

@SuppressWarnings("unchecked")

public GraphPP(int V) {

if (V < 0) throw new Error("Number of vertices must be nonnegative");

aloll = new ArrayList();

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

LinkedList aLinkedList = new LinkedList();

aloll.add(aLinkedList);

}

}

/* V

* return the number of vertices in the graph

*/

public int V() { return aloll.size(); } // the arrayList knows its size

/**

* Add the undirected edge v-w to graph.

* @throws java.lang.IndexOutOfBoundsException unless both 0 <= v < V and 0 <= w < V

*

* enforces no self loops or parallel edges

* verifies that v,w are valid vertices - throws an exception if not

*

* return true if edge was successfully added

* return false otherwise

*/

public boolean addEdge(int v, int w) {

if (v < 0 || v >= this.V()) throw new IndexOutOfBoundsException();

if (w < 0 || w >= this.V()) throw new IndexOutOfBoundsException();

if ( v == w ) return false; // ?

if ( aloll.get(v).contains(w)) return false; // what is this 'trying' to do?

// add w to v's list and v to w's list

LinkedList veesAdjList = aloll.get(v); // get a reference to v's list from the arrayList

veesAdjList.add(w); // add w to v's list

aloll.get(w).add(v); // one-line version of the above to add v to w's list

return true;

}

/**

* delete the undirected edge v-w from the graph

*

* verifies that v,w are valid vertices - throw an exception if not

*

* return true if edge was successfully deleted

* return false otherwise

*/

public boolean deleteEdge(int v, int w) {

if (v < 0 || v >= this.V()) throw new IndexOutOfBoundsException();

if (w < 0 || w >= this.V()) throw new IndexOutOfBoundsException();

boolean delw = aloll.get(v).remove( (Integer) w); // uses Object version of remove

int indexOfV = aloll.get(w).indexOf(v); // get the 'index' of v within w's list

int remValue = aloll.get(w).remove(indexOfV); // uses Index version of remove

if ( delw && remValue == v ) {

return true;

}

else

return false;

}

/*

* hasEdge

* Determine if the graph has an edge between v,w

* return true if edge exists

* return false otherwise

*/

public boolean hasEdge(int v,int w) {

if (aloll.get(v).contains(w) && aloll.get(w).contains(v) )

return true;

return false;

}

/* add Vertex

*

* adds a vertex to the graph.

* return: the numerical index of the newly added vertex

*

*/