public class GraphPP {// Graph++- incrementally better than the old Graph private int V; // number of
Question:
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
private LinkedList
/*
*/
@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
}
/*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
// 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;
}
}
Practical Introduction To Data Structures And Algorithm Analysis Java Edition
ISBN: 9780136609117
1st Edition
Authors: Clifford A. Shaffer