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

private int V; // number of actual vertices

private int E;// actual number of edges

private ArrayList[] adjE;// enhanced adjacency list

private LinkedListav;// available vertex values list

/*

*/

@SuppressWarnings("unchecked")

public GraphPP(int V) {

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

this.V = V;

this.E = 0;

adjE = new ArrayList[V];// ToDo 0.1Comment this line of code

for (int i=0; i < V; i++) {// ToDo 0.2Comment this line of code

adjE[i] = new ArrayList();

}

av = new LinkedList();// ToDo 0.3 Comment this line of code

}

/*V

*return the number of vertices in the graph

*/

public int V() { return V; }

/*

* Return the number of edges in the graph.

*/

public int E() { return E;}

/* isValid

*

* returns true if the parameter v is a valid current vertex value, false otherwise

* if a vertex is deleted, we mark it "Invalid" since that value is not referring to an actual current vertex

*/

private boolean isValid(int v) {

if ( v < 0 || v >= V) return false;

return ! av.contains(v);

}

/**

* Add the undirected edge v-w to graph.

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

*

* MUST:

*enforces no self loops or parallel edges

*verify that v,w are valid vertices - throw 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 >= V) throw new IndexOutOfBoundsException();

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

//ToDo 1.implement this method

return false;

}

/**

* delete the undirected edge v-w from the graph

*

* MUST:

*enforces no self loops or parallel edges

*verify 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) {

//ToDo 2.implement this method

return false;

}

/*

* hasEdge

*Determine if the graph has an edge betweenv,w

*return true if v,w are valid and edge exists

*return false otherwise(don't throw an exception )

*/

public boolean hasEdge(int v,int w) {

//ToDo 3.implement this method

return false;

}

/* add Vertex

*

* adds a vertex to the graph.

* the new vertex can come from:

*a) the available vertex list(if there are any)

*b) resizing the adjE array.For testing purposes, you only should increase the size by 1!

*

*return:the numerical index of the newly added vertex

*

*fair number of issues here

*/

public intaddVertex() {

//ToDo 4implement this method

return -1;

}

/* deleteVertex

*

* MUST:

*remove vertex v if it exists

*AND also remove all edges involving vertex v

*

*vertex v is added to the 'available vertex' list

*AND there is now 1 fewer vertex in the graph

*

* returns:

*true if successful

*false if v was invalid//don't throw an exception

*/

public boolean deleteVertex(int v) {

//ToDo 5implement this method

return false;

}

/*

* adj

*

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

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

*/

public Iterable adj(int v) {

// ToDo 6 fix/implement this method

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

return null;

}

/*

* You are responsible for testing.

*

* The following is just to get you started

*

*/

public static void main(String[] args) {

try {// put in a try catch block to test that exceptions are thrown correctly

constructorTest();

}

catch (Exception e) {

StdOut.println(" Exception occured in constuctor test: " + e.getMessage());;

}

}

/*

* Constructor test

*

* reads graph info from file:

*prints the file contents

*actual graph data fromadjacency lists

*

*requires correct implementation ofadj method

*

*/

public static void constructorTest() {

String fileName;

fileName = "data/tinyG.txt";

// fileName = "data/tinyCG.txt";

// test constructor usingfromIn

StdOut.println( "FromIn test.graph data from file");

In in = new In(fileName);

while (! in.isEmpty()) {

StdOut.println( in.readLine());

}

in = new In(fileName);

GraphPP G = fromIn(in);// create graph from data file

StdOut.println( "actual graph info");

StdOut.println( G);

//G.toGraphviz ("g.png");

}

/* **********************************************************************

*utility routines;look but don't alter

*/

/**

* Return a string representation of the graph.

*/

public String toString() {

StringBuilder s = new StringBuilder();

String NEWLINE = System.getProperty("line.separator");

s.append(V + " vertices, " + E() + " edges " + NEWLINE);

for (int v = 0; v < adjE.length; v++) {

if ( ! av.contains(v) ){

s.append(v + ": ");

for (int w : adjE[v]) {

s.append(w + " ");

}

s.append(NEWLINE);

}

}

return s.toString();

}

/**

* Save a graphviz representation of the graph.

* See graphviz.org.

*/

public void toGraphviz(String filename) {

GraphvizBuilder gb = new GraphvizBuilder ();

for (int v = 0; v < adjE.length; v++) {

if (! av.contains(v)) {

gb.addNode (v);

boolean showSelfLoop = false;

for (int w : adjE[v]) {

if (v < w) // only once each edge

gb.addEdge (v, w);

if (v == w) {

showSelfLoop = !showSelfLoop;

if (showSelfLoop)

gb.addEdge (v, w);

}

}

} // if valid

}

gb.toFileUndirected (filename);

}

/* fromIn

*

* create an GraphPP from an input file

*

* requires addEdge for correct operation

*/

public static GraphPP fromIn (In in) {

GraphPP G = new GraphPP (in.readInt());

int E = in.readInt();

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

int v = in.readInt();

int w = in.readInt();

G.addEdge(v, w);

}

return G;

}

}