How do I write a minEdges method that returns the minimum number of edges that e

ID: 3820925 • Letter: H

Question

How do I write a minEdges method that returns the minimum number of edges that exist on a path between two given vertices. Then add the method to the useGraph class? The shortestPaths method is concerned with the minimum distance between two vertices of a graph.

package ch10.apps;

import ch04.queues.*;
import ch02.stacks.*;
import ch10.graphs.*;
import ch09.priorityQueues.*;
import support.Flight;

public class UseGraph
{
private static void shortestPaths(WeightedGraphInterface graph,
String startVertex )
// Writes the shortest distance from startVertex to every
// other reachable vertex in graph.
{
Flight flight;
Flight saveFlight; // for saving on priority queue
int minDistance;
int newDistance;

PriQueueInterface pq = new HeapPriQ(20); // Assume at most 20 vertices
String vertex;
QueueInterface vertexQueue = new LinkedQueue();

graph.clearMarks();
saveFlight = new Flight(startVertex, startVertex, 0);
pq.enqueue(saveFlight);

System.out.println("Last Vertex Destination Distance");
System.out.println("------------------------------------");

do
{
flight = pq.dequeue();
if (!graph.isMarked(flight.getToVertex()))
{
graph.markVertex(flight.getToVertex());
System.out.println(flight);
flight.setFromVertex(flight.getToVertex());
minDistance = flight.getDistance();
vertexQueue = graph.getToVertices(flight.getFromVertex());
while (!vertexQueue.isEmpty())
{
vertex = vertexQueue.dequeue();
if (!graph.isMarked(vertex))
{
newDistance = minDistance
+ graph.weightIs(flight.getFromVertex(), vertex);
saveFlight = new Flight(flight.getFromVertex(), vertex, newDistance);
pq.enqueue(saveFlight);
}
}
}
} while (!pq.isEmpty());
System.out.println();
System.out.println("The unreachable vertices are:");
vertex = graph.getUnmarked();
while (vertex != null)
{
System.out.println(vertex);
graph.markVertex(vertex);
vertex = graph.getUnmarked();
}
System.out.println();
}

private static boolean isPathDF(WeightedGraphInterface graph,
String startVertex,
String endVertex )
// Returns true if a path exists on graph, from startVertex to endVertex;
// otherwise returns false. Uses depth-first search algorithm.
{
StackInterface stack = new LinkedStack();
QueueInterface vertexQueue = new LinkedQueue();

boolean found = false;
String currVertex; // vertex being processed
String adjVertex; // adjacent to currVertex

graph.clearMarks();
graph.markVertex(startVertex);
stack.push(startVertex);

do
{
currVertex = stack.top();
stack.pop();
System.out.println(currVertex);
if (currVertex.equals(endVertex))
found = true;
else
{
vertexQueue = graph.getToVertices(currVertex);
while (!vertexQueue.isEmpty())
{
adjVertex = vertexQueue.dequeue();
if (!graph.isMarked(adjVertex))
{
graph.markVertex(adjVertex);
stack.push(adjVertex);
}
}
}
} while (!stack.isEmpty() && !found);

return found;
}

private static boolean isPathBF(WeightedGraphInterface graph,
String startVertex,
String endVertex )

// Returns true if a path exists on graph, from startVertex to endVertex;
// otherwise returns false. Uses breadth-first search algorithm.

{
QueueInterface queue = new LinkedQueue();
QueueInterface vertexQueue = new LinkedQueue();

boolean found = false;
String currVertex; // vertex being processed
String adjVertex; // adjacent to currVertex

graph.clearMarks();
graph.markVertex(startVertex);
queue.enqueue(startVertex);

do
{
currVertex = queue.dequeue();
System.out.println(currVertex);
if (currVertex.equals(endVertex))
found = true;
else
{
vertexQueue = graph.getToVertices(currVertex);
while (!vertexQueue.isEmpty())
{
adjVertex = vertexQueue.dequeue();
if (!graph.isMarked(adjVertex))
{
graph.markVertex(adjVertex);
queue.enqueue(adjVertex);
}
}
}
} while (!queue.isEmpty() && !found);

return found;
}

public static void main(String[] args)
{
// Create and analyze grph in Figure 10.3
System.out.println("Creating graph in figure 10.3");
WeightedGraphInterface graph = new WeightedGraph();
String s0 = new String("Atlanta ");
String s1 = new String("Austin ");
String s2 = new String("Chicago ");
String s3 = new String("Dallas ");
String s4 = new String("Denver ");
String s5 = new String("Houston ");
String s6 = new String("Washington");

graph.addVertex(s0);
graph.addVertex(s1);
graph.addVertex(s2);
graph.addVertex(s3);
graph.addVertex(s4);
graph.addVertex(s5);
graph.addVertex(s6);

graph.addEdge(s0, s5, 800);
graph.addEdge(s0, s6, 600);
graph.addEdge(s1, s3, 200);
graph.addEdge(s1, s5, 160);
graph.addEdge(s2, s4, 1000);
graph.addEdge(s3, s1, 200);
graph.addEdge(s3, s2, 900);
graph.addEdge(s3, s4, 780);
graph.addEdge(s4, s0, 1400);
graph.addEdge(s4, s2, 1000);
graph.addEdge(s5, s0, 800);
graph.addEdge(s6, s0, 600);
graph.addEdge(s6, s3, 1300);

boolean result;

System.out.println(s6 + " to " + s3);
result = isPathDF(graph, s6, s3);
System.out.println(result);
System.out.println();

System.out.println(s6 + " to " + s1);
result = isPathDF(graph, s6, s1);
System.out.println(result);
System.out.println();

System.out.println();
System.out.println("Determining path using breadth first ...");
System.out.println();

System.out.println(s1 + " to " + s2);
result = isPathBF(graph, s1, s2);
System.out.println(result);
System.out.println();

System.out.println(s1 + " to " + s6);
result = isPathBF(graph, s1, s6);
System.out.println(result);
System.out.println();

System.out.println(s3 + " to " + s1);
result = isPathBF(graph, s3, s1);
System.out.println(result);
System.out.println();

System.out.println(s0 + " to " + s4);
result = isPathBF(graph, s0, s4);
System.out.println(result);
System.out.println();

System.out.println(s6 + " to " + s3);
result = isPathBF(graph, s6, s3);
System.out.println(result);
System.out.println();

System.out.println(s6 + " to " + s1);
result = isPathBF(graph, s6, s1);
System.out.println(result);

System.out.println();
System.out.println();
System.out.println("Shortest paths starting at " + s6);
shortestPaths(graph, s6);

System.out.println();
System.out.println();
System.out.println("Shortest paths starting at " + s4);
shortestPaths(graph, s4);

System.out.println();
System.out.println();

// Create and analyze graph in Figure 10.x
System.out.println("Creating graph in figure 10.x");
graph = new WeightedGraph();
s0 = new String("Atlanta ");
s1 = new String("Austin ");
s2 = new String("Chicago ");
s3 = new String("Dallas ");
s4 = new String("Denver ");
s5 = new String("Houston ");
s6 = new String("Washington");

graph.addVertex(s0);
graph.addVertex(s1);
graph.addVertex(s2);
graph.addVertex(s3);
graph.addVertex(s4);
graph.addVertex(s5);
graph.addVertex(s6);

System.out.println("Determining path using depth first ...");
System.out.println();

System.out.println(s1 + " to " + s2);
result = isPathDF(graph, s1, s2);
System.out.println(result);
System.out.println();

System.out.println(s1 + " to " + s6);
result = isPathDF(graph, s1, s6);
System.out.println(result);
System.out.println();

System.out.println(s6 + " to " + s5);
result = isPathDF(graph, s6, s5);
System.out.println(result);
System.out.println();

System.out.println(s6 + " to " + s3);
result = isPathDF(graph, s6, s3);
System.out.println(result);
System.out.println();

System.out.println(s6 + " to " + s1);
result = isPathDF(graph, s6, s1);
System.out.println(result);
System.out.println();

System.out.println();
System.out.println("Determining path using breadth first ...");
System.out.println();

System.out.println(s1 + " to " + s2);
result = isPathBF(graph, s1, s2);
System.out.println(result);
System.out.println();

System.out.println(s1 + " to " + s6);
result = isPathBF(graph, s1, s6);
System.out.println(result);
System.out.println();

System.out.println(s6 + " to " + s5);
result = isPathBF(graph, s6, s5);
System.out.println(result);
System.out.println();

System.out.println(s6 + " to " + s3);
result = isPathBF(graph, s6, s3);
System.out.println(result);
System.out.println();

System.out.println(s6 + " to " + s1);
result = isPathBF(graph, s6, s1);
System.out.println(result);

System.out.println();
System.out.println();
System.out.println("Shortest paths starting at " + s6);
shortestPaths(graph, s6);

System.out.println();
System.out.println();
System.out.println("Shortest paths starting at " + s4);
shortestPaths(graph, s4);

System.out.println();

}
}

Explanation / Answer

Please find the below methods for the above problem statement:

For your easiness I will post two ways to achieve it:

Way 01:

Kindly note that minedges are calculated by the difference between two end points of the vertex.

**************************

public static ArrayList<String> minEdges(Vertex target)
{
ArrayList<String> path = new ArrayList<String>();
for (Vertex vertex = target; vertex != null; vertex = vertex.previous)
{
path.add(vertex.name + "=" + vertex.getDistFromPrev());
}
Collections.reverse(path);
return path;
}

public double getDistFromPrev()
{
double weight = 0.;
for(Edge e : adjacencies){
if(e.target == this.previous){
weight = e.weight;
}
}
return weight;
}

**********************

Way 02:

*********************************

public void shortestPath(Vertex startVertex) {
startVertex.setMinDistance(0);
PriorityQueue<Vertex> queue = new PriorityQueue<>();
queue.add(startVertex);

while (!queue.isEmpty()) {
Vertex actualVertex = queue.poll();

for (Edge edge : actualVertex.getAdjacencyList()) {
Vertex v = edge.getTargetVertex();
double weight = edge.getWeight();
double currentDistance = actualVertex.getMinDistance() + weight;

if (currentDistance < v.getMinDistance()) {
queue.remove(v);
v.setMinDistance(currentDistance);
v.setPreviousVertex(actualVertex);
queue.add(v);
}
}
}
}

public List<Vertex> getShortestPathTo(Vertex targetVertex){
List<Vertex> path = new ArrayList<Vertex>();
for (Vertex vertex = targetVertex; vertex != null; vertex = vertex.getPreviousVertex()){
path.add(vertex);
}
Collections.reverse(path);
return path;
}
}

***********************************

P.S KINDLY ADD THE SUITABLE WAY IN YOUR MAINCLASS

Navigate

How do I write a java search and replace word program without using Arrays, gene

How do I write a program code in C program properly. Ever time put a code in it

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

How do I write a minEdges method that returns the minimum number of edges that e

Question

Explanation / Answer

Related Questions

Navigate