Question: import java.util.*; import java.io.*; class Vertex { // Constructor: set name, chargingStation and index according to given values, // initilaize incidentRoads as empty array public
import java.util.*;
import java.io.*;
class Vertex {
// Constructor: set name, chargingStation and index according to given values,
// initilaize incidentRoads as empty array
public Vertex(String placeName, boolean chargingStationAvailable, int idx) {
name = placeName;
incidentRoads = new ArrayList
index = idx;
chargingStation = chargingStationAvailable;
}
public Vertex(String placeName, boolean hasChargingStataion) {
}
public String getName() {
return name;
}
public boolean hasChargingStation() {
return chargingStation;
}
public ArrayList
return incidentRoads;
}
// Add a road to the array incidentRoads
public void addIncidentRoad(Edge road) {
incidentRoads.add(road);
}
public int getIndex() {
return index;
}
private String name; // Name of the place
ArrayList
private boolean chargingStation; // Availability of charging station
private int index; // Index of this vertex in the vertex array of the map
public void setVisited(boolean b) {
}
public Edge[] getAdjacentEdges() {
return null;
}
public boolean isVisited() {
return false;
}
public boolean isChargingStationAvailable() {
return false;
}
}
class Edge {
public Edge(int roadLength, Vertex firstPlace, Vertex secondPlace) {
length = roadLength;
incidentPlaces = new Vertex[] { firstPlace, secondPlace };
}
public Edge(Vertex vtx1, Vertex vtx2, int length2) {
}
public Vertex getFirstVertex() {
return incidentPlaces[0];
}
public Vertex getSecondVertex() {
return incidentPlaces[1];
}
public int getLength() {
return length;
}
private int length;
private Vertex[] incidentPlaces;
public Vertex getEnd() {
return null;
}
}
//A class that represents a sparse matrix
public class RoadMap {
// Default constructor
public RoadMap() {
places = new ArrayList
roads = new ArrayList
}
// Auxiliary function that prints out the command syntax
public static void printCommandError() {
System.err.println("ERROR: use one of the following commands");
System.err.println(" - Load a map and print information:");
System.err.println(" java RoadMap -i
System.err.println(" - Load a map and determine if two places are connnected by a path with charging stations:");
System.err.println(" java RoadMap -c
System.err.println(" - Load a map and determine the mininmum number of assistance cars required:");
System.err.println(" java RoadMap -a
}
public static void main(String[] args) throws Exception {
if (args.length == 2 && args[0].equals("-i")) {
RoadMap map = new RoadMap();
try {
map.loadMap(args[1]);
} catch (Exception e) {
System.err.println("Error in reading map file");
System.exit(-1);
}
System.out.println();
System.out.println("Read road map from " + args[1] + ":");
map.printMap();
System.out.println();
}
else if (args.length == 2 && args[0].equals("-a")) {
RoadMap map = new RoadMap();
try {
map.loadMap(args[1]);
} catch (Exception e) {
System.err.println("Error in reading map file");
System.exit(-1);
}
System.out.println();
System.out.println("Read road map from " + args[1] + ":");
map.printMap();
int n = map.minNumAssistanceCars();
System.out.println();
System.out.println("The map requires at least " + n + " assistance car(s)");
System.out.println();
}
else if (args.length == 4 && args[0].equals("-c")) {
RoadMap map = new RoadMap();
try {
map.loadMap(args[1]);
} catch (Exception e) {
System.err.println("Error in reading map file");
System.exit(-1);
}
System.out.println();
System.out.println("Read road map from " + args[1] + ":");
map.printMap();
int startVertexIdx = -1, endVertexIdx = -1;
try {
startVertexIdx = Integer.parseInt(args[2]);
endVertexIdx = Integer.parseInt(args[3]);
} catch (NumberFormatException e) {
System.err.println("Error: start vertex and end vertex must be specified using their indices");
System.exit(-1);
}
if (startVertexIdx < 0 || startVertexIdx >= map.numPlaces()) {
System.err.println("Error: invalid index for start vertex");
System.exit(-1);
}
if (endVertexIdx < 0 || endVertexIdx >= map.numPlaces()) {
System.err.println("Error: invalid index for end vertex");
System.exit(-1);
}
Vertex startVertex = map.getPlace(startVertexIdx);
Vertex endVertex = map.getPlace(endVertexIdx);
if (!map.isConnectedWithChargingStations(startVertex, endVertex)) {
System.out.println();
System.out.println("There is no path connecting " + map.getPlace(startVertexIdx).getName() + " and "
+ map.getPlace(endVertexIdx).getName() + " with charging stations");
} else {
System.out.println();
System.out.println("There is at least one path connecting " + map.getPlace(startVertexIdx).getName() + " and "
+ map.getPlace(endVertexIdx).getName() + " with charging stations");
}
System.out.println();
} else {
printCommandError();
System.exit(-1);
}
}
public void loadMap(String filename) {
File file = new File(filename);
places.clear();
roads.clear();
try {
Scanner sc = new Scanner(file);
//Read the first line: number of vertices and number of edges
int numVertices = sc.nextInt();
int numEdges = sc.nextInt();
for (int i = 0; i < numVertices; ++i) {
// Read the vertex name and its charing station flag
String placeName = sc.next();
int charginStationFlag = sc.nextInt();
boolean hasChargingStataion = (charginStationFlag == 1);
// Create a new vertex using the information above and add it to places
Vertex newVertex = new Vertex(placeName, hasChargingStataion, i);
places.add(newVertex);
}
for (int j = 0; j < numEdges; ++j) {
// Read the edge length and the indices for its two vertices
int vtxIndex1 = sc.nextInt();
int vtxIndex2 = sc.nextInt();
int length = sc.nextInt();
Vertex vtx1 = places.get(vtxIndex1);
Vertex vtx2 = places.get(vtxIndex2);
Edge newEdge = new Edge(length, vtx1, vtx2);
Edge reverseEdge = new Edge(length, vtx2, vtx1);
vtx1.addIncidentRoad(newEdge);
vtx2.addIncidentRoad(reverseEdge);
roads.add(newEdge);
}
sc.close();
} catch (Exception e) {
e.printStackTrace();
places.clear();
roads.clear();
}
}
the question is :
//Check if two vertices are connected by a path with charging stations on each itermediate vertex.
//Return true if such a path exists; return false otherwise.
//The worst-case time complexity of your algorithm should be no worse than O(v + e),
//where v and e are the number of vertices and the number of edges in the graph.
starting with
public boolean isConnectedWithChargingStations(Vertex startVertex, Vertex endVertex) {
if (startVertex.getIndex() == endVertex.getIndex()) {
return true;
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help