We wish to expand the class SimpleGraph, shown in Figure 9.14, to include method
ID: 3581387 • Letter: W
Question
We wish to expand the class SimpleGraph, shown in Figure 9.14, to include methods to delete a vertex, delete an edge, fetch a vertex, fetch an edge, update an edge, update a vertex. Modify the class SimpleGraph so that it can store a weighted graph. a. Give the pseudocode of the methods' algorithms. b. Extend the code of the class SimpleGraph, to include the new methods and write a simple application to demonstrate they function properly. Use the author's version of SimpleGraph (attached) as your starting point and add the methods requested. For part A the pseudocode represent your up front thinking on this problem.
Figure 9.14
public class SimpleGraph // a directed graph
{
Listing vertex[ ]; //the reference to the vertex array
int edge[ ][ ]; // reference to the adjacency matrix array
int max, numberOfVertices;
public SimpleGraph(int n)
{
vertex = new Listing[n]; // allocation of the vertex array
edge = new int[n][n]; // adjacency matrix with all elements set to 0
max = n; numberOfVertices = 0;
}
public boolean insertVertex(int vertexNumber, Listing newListing)
{
if (vertexNumber >= max) //the graph is full
return false;
vertex[vertexNumber] = newListing.deepCopy(); numberOfVertices++;
return true;
}
public boolean deleteVertex(int vertexNumber)
{
vertex[vertexNumber] = null;
return true;
}
public boolean insertEdge(int fromVertex, int toVertex)
{
if(vertex[fromVertex] == null || vertex[toVertex] == null) // non-existent vertex
return false;
edge[fromVertex][toVertex] = 1;
return true;
}
public boolean deleteEdge(int firstVertex, int secondVertex)
{
if(vertex[firstVertex] == null || vertex[secondVertex] == null) // non-existent vertex
return false;
edge[firstVertex][secondVertex] = 0;
return true;
}
public void showVertex(int vertexNumber)
{
System.out.println(vertex[vertexNumber]);
}
public void showEdges(int vertexNumber) //edges emanating from vertexNumber
{
for(int column=0;
column
{
if(edge[vertexNumber][column] == 1) // there is an edge
System.out.println(vertexNumber + "," + column);
}
}
}// end of SimpleGraph class
Explanation / Answer
class SimpleGraph
{
Listing vertex[];
int edge[][];
int max, numberOfVertices;
public SimpleGraph(int n)
{
vertex = new Listing[n];
edge = new int[n][n];
max = n;
numberOfVertices = 0;
}
public boolean insertVertex(int vertexNumber, Listing newListing)
{
if(vertexNumber >= max)
return false;
vertex[vertexNumber] = newListing.deepCopy();
numberOfVertices++;
return true;
}
public boolean insertEdge(int fromVertex, int toVertex)
{
if(vertex[fromVertex] == null || vertex[toVertex] == null)
return false;
edge[fromVertex][toVertex] = 1;
return true;
}
public void showVertex(int vertexNumber)
{
System.out.println(vertex[vertexNumber]);
}
public void showEdges(int vertexNumber)
{
for(int column = 0; column < numberOfVertices; column++)
{
if(edge[vertexNumber][column] == 1)
System.out.println(vertexNumber + "," + column);
}
}
public static void main(String[] args)
{
SimpleGraph flyUS = new SimpleGraph(5);
Listing v0 = new Listing("Philadelphia");
Listing v1 = new Listing("New York");
Listing v2 = new Listing("Boston");
Listing v3 = new Listing("Los Angeles");
Listing v4 = new Listing("Houston");
flyUS.insertVertex(0, v0);
flyUS.insertVertex(1, v1);
flyUS.insertVertex(2, v2);
flyUS.insertVertex(3, v3);
flyUS.insertVertex(4, v4);
flyUS.insertEdge(0,1);
flyUS.insertEdge(0,3);
flyUS.insertEdge(1,2);
flyUS.insertEdge(1,3);
flyUS.insertEdge(2,1);
flyUS.insertEdge(3,1);
flyUS.insertEdge(3,4);
flyUS.insertEdge(4,0);
flyUS.insertEdge(4,3);
for(int i = 0; i < 5; i++)
{
System.out.print("hub " + i + "'s ");
flyUS.showVertex(i);
System.out.println("its routes are: ");
flyUS.showEdges(i);
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.