We wish to expand the class SimpleGraph, shown in Figure 9.14, to include method

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

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.