implement adjacency matrix representation. import java.util.ArrayList; /** * Gra
ID: 657958 • Letter: I
Question
implement adjacency matrix representation.
import java.util.ArrayList;
/**
* Graph_Cities.java
*
* This class represents a graph of roads
* between cities.
*
* Complete the addRoads, getRoadDuration,
* getTopologicalOrdering, and hasCycle methods.
*
* You must use an adjacency matrix representation
* of a graph.
*/
public class Graph_Cities
{
// 0.0f = no road
// So if roads[a][b] = 0.0f then there is no edge
private float[][] roads;
private int vertexCount;
// do not add additional instance variables
public Graph_Cities(int vertexCount)
{
this.vertexCount = vertexCount;
this.roads = new float[vertexCount][vertexCount];
}
/**
* Add a road (weight) between two cities.
*
* @param a the start city (index)
* @param b the end city (index)
* @param duration the weight of the road
*/
public void addRoad(int a, int b, float duration)
{
// YOUR CODE HERE
}
/**
* Return the duration (weight) of a road.
*
* @param a start city (index)
* @param b end city (index)
* @return the weight between the two cities
*/
public float getRoadDuration(int a, int b)
{
// YOUR CODE HERE
}
/**
* getTopologicalOrdering.
*
* Return a topological ordering of the graph.
*
* You can assume that the graph doesn't have
* any cycles.
*
* The returned arraylist should contain a
* list of indexes in topoligical order.
*
* TIP: Do this method last. It is the most
* difficult, but it is only worth a fraction
* of the total points.
*
* @return a topological ordering of the graph
*/
public ArrayList getTopologicalOrdering()
{
// YOUR CODE HERE
}
/**
* hasCycle.
*
* Return true if the graph contains a cycle.
*
* Use Depth-First Search to check for cycles.
*
* This will require a recursive helper method
* that you can define however you like.
*
* @return true if the graph contains a cycle, or false otherwise
*/
public boolean hasCycle()
{
// YOUR CODE HERE
}
}
public class Tester
{
public static void main(String[] args)
{
Graph_Cities g = new Graph_Cities(5);
g.addRoad(0, 1, 1.0f);
g.addRoad(1, 2, 2.0f);
g.addRoad(1, 4, 1.0f);
g.addRoad(2, 3, 1.0f);
g.addRoad(3, 4, 2.0f);
System.out.printf("Actual: %.2f%n", g.getRoadDuration(1, 2));
System.out.printf("Expected: 2.00%n");
System.out.printf("Actual: %.2f%n", g.getRoadDuration(2, 3));
System.out.printf("Expected: 1.00%n");
System.out.println("Actual: " + g.getTopologicalOrdering());
System.out.println("Expected: [0, 1, 2, 3, 4]");
System.out.println("Actual: " + g.hasCycle());
System.out.println("Expected: false");
g.addRoad(4, 0, 1.0f);
System.out.println("Actual: " + g.hasCycle());
System.out.println("Expected: true");
g = new Graph_Cities(5);
g.addRoad(0, 3, 1.0f);
g.addRoad(3, 1, 2.0f);
g.addRoad(1, 2, 1.0f);
g.addRoad(2, 4, 1.0f);
System.out.println("Actual: " + g.getTopologicalOrdering());
System.out.println("Expected: [0, 3, 1, 2, 4]");
}
}
Explanation / Answer
implement adjacency matrix representation.
import java.util.ArrayList;
/**
* Graph_Cities.java
*
* This class represents a graph of roads
* between cities.
*
* Complete the addRoads, getRoadDuration,
* getTopologicalOrdering, and hasCycle methods.
*
* You must use an adjacency matrix representation
* of a graph.
*/
public class Graph_Cities
{
// 0.0f = no road
// So if roads[a][b] = 0.0f then there is no edge
private float[][] roads;
private int vertexCount;
// do not add additional instance variables
public Graph_Cities(int vertexCount)
{
this.vertexCount = vertexCount;
this.roads = new float[vertexCount][vertexCount];
}
public void addRoad(int a, int b, float duration)
{roads[a][b]=duration; }
public float getRoadDuration(int a, int b)
{
return roads[a][b];
}
public ArrayList<Integer> getTopologicalOrdering()
{ ArrayList<Integer> topo=new ArrayList<Integer>();
int i=1;
while(i<=vertexCount)
{int j=i+1;
if(roads[i][j]==0.0f){i=i+1;j=i+1;}
else{
topo.add(roads[i][j]);
temp=i;i=j;j=temp;}
}return topo;
}
public boolean hasCycle()
{boolean cycle;
for(int i=1;i<=vertexCount;i++){
for(int j=1;j<=vertexCount;j++){
if(i==j)
{if(roads[i][j]!=0.0f){cycle=false;}
}}}
if(i==vertexCount+1){return cycle;}
}
}
import Assignment_05.Graph_Airports;
public class Tester
{
public static void main(String[] args)
{
Graph_Airports g = new Graph_Airports(5);
g.addRoad(0, 1, 1.0f);
g.addRoad(1, 2, 2.0f);
g.addRoad(1, 4, 1.0f);
g.addRoad(2, 3, 1.0f);
g.addRoad(3, 4, 2.0f);
System.out.printf("Actual: %.2f%n", g.getRoadDuration(1, 2));
System.out.printf("Expected: 2.00%n");
System.out.printf("Actual: %.2f%n", g.getRoadDuration(2, 3));
System.out.printf("Expected: 1.00%n");
System.out.println("Actual: " + g.getTopologicalOrdering());
System.out.println("Expected: [0, 1, 2, 3, 4]");
System.out.println("Actual: " + g.hasCycle());
System.out.println("Expected: false");
g.addRoad(4, 0, 1.0f);
System.out.println("Actual: " + g.hasCycle());
System.out.println("Expected: true");
g = new Graph_Airports(5);
g.addRoad(0, 3, 1.0f);
g.addRoad(3, 1, 2.0f);
g.addRoad(1, 2, 1.0f);
g.addRoad(2, 4, 1.0f);
System.out.println("Actual: " + g.getTopologicalOrdering());
System.out.println("Expected: [0, 3, 1, 2, 4]");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.