each ToDo's orders of growth with explanations. Please refrain
from copying past answers from similar questions and come up
with a new one because the others don't work which is why I am
posting.
NOTE: I didn't include all functions, just the class info and
ToDo functions because answers won't let me. Please ask if you have
any questions and maybe I'll have to upload images instead.
NOTE: The Graph being used in this code is built from the
information from the text file named tinyG.txt and the
contents in tinyG are pasted below:
13
13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3
-------end of file--------
The only imported modules are:
import java.util.ArrayList;
import java.util.LinkedList;
import algs41.Graph;
import algs41.GraphGenerator;
public class GraphPP { // Graph++ - incrementally
better than the old Graph
// V, E instance variables are not here!
private
ArrayList<LinkedList<Integer>> 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<Integer> 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
/*
* 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() {
// ToDo 1: 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<Integer> adj(int v)
{
// ToDo 2 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) {
//ToDo 3 implement
this method
return false;
}
public static void main(String[] args) {
// comment in/out while
working on various ToDos
constructorTest(); // just for reference
//ETests();
//adjTests();
//deleteVertexTests();
}