In: Computer Science
Please provide the answer in Java
1. Consider the following scenario: The Colonel Motors Corporation of Frankfort, Kentucky has produced a new line of vehicles which require chicken droppings for fuel. Because of this unusual fuel requirement, there are only certain fueling stations in the country where the vehicles can be refilled. Thus, to get from one place to another, an owner must plan a route that ensures that he can get refills along the way. The Colonel Motors Corporation has hired Professor Sanders of the Kentucky Institute of Technology as a consultant to prepare an online route-finding service. To use the computerized service, an owner will enter the driving range of his vehicle (the distance the vehicle can go on a single fill-up), the "distance to empty" (the distance the vehicle can go with the fuel that's now in the tank), his/her initial location (source), and his/her desired destination. The service will either respond with a shortest route from the source to the destination such that the owner never runs out of fuel, or it will deem that no such route exists. Model the professor's problem in terms of a weighted, directed graph in which streets are edges, intersections are vertices, and some intersections have fueling stations, and design an efficient algorithm to solve it. Assume that a driver's source and destination are also at intersections.
2. Choose an appropriate problem-solving technique: Select your favorite programming language such as C, C++, or Java. In that language, write, implement, and test an algorithm using the problem solving technique that you chose. Analyze your implementation using either order notation analysis or empirical analysis. You must prepare a separate page providing the instructions to compile and execute your program, such as the development environment (e.g., Visual Studio). If no such information is provided, and your program fails to build and run, points will be deducted, as appropriate.
HELLO ADDING WHOLE WORKING JAVA CODE HERE
PLEASE GO TROUGH IT ONCE
AND PLEASE PROVIDE ADJACENCYMATRIX IN FILE NAMED adjacencymatrix.txt
HERE IS THE CODE
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;
class GraphUtility {
public static void main(String[] args) {
// TODO Auto-generated method stub
try {
//readFromFile();
} catch(Exception ex0)
{
ex0.toString();
}
}
public static void swap(int[] array, int i, int j) {
int tempO = array[i];
array[i] = array[j];
array[j] = tempO;
}
//Util Function
public static int[] listToArray(List<Integer> list)
{
int[] tempArray = new int[list.size()];
for(int i = 0; i < list.size(); i++)
{
tempArray[i] = list.get(i);
}
return tempArray;
}
public static int[] readFuelInfo() throws FileNotFoundException
{
Scanner scan = new Scanner(new File("fuels.txt"));
String strInput = "";
List<Integer> arrayValues = new ArrayList<Integer>();
if(scan.hasNextLine()) {
strInput = scan.nextLine();
String[] tempValues = strInput.split(",");
for(int i = 0; i < tempValues.length; i++)
{
try
{
arrayValues.add(Integer.parseInt(tempValues[i].trim()));
}
catch(Exception ex0){}
}
}
int[] fuelData = listToArray(arrayValues);
System.out.println(fuelData.length > 0 ? ("fuel stations: " + Arrays.toString(fuelData)) : "no fuel stations found.");
return fuelData;
}
public static GraphData readGraph() throws FileNotFoundException
{
Scanner scan = new Scanner(new File("adjacencymatrix.txt"));
int V = scan.nextInt();
scan.nextLine();
double[][] adjacencyMatrix = new double[V][V];
for (int v = 0; v < V; v++) {
for (int e = 0; e < V; e++) {
adjacencyMatrix[v][e] = scan.nextDouble();
}
}
return new GraphData(V, adjacencyMatrix);
}
}
class PathComponent {
private int s;
private int d;
public PathComponent(int s, int d) {
this.s = s;
this.d = d;
}
public int getSource() {
return this.s;
}
public int getDestination() {
return this.d;
}
}
class IntermediatePath {
private String stringPath;
private IntersectionNode[] nodes;
private List<PathComponent> paths;
private int s;
private int d;
private double totalWeight;
public IntermediatePath(int sourceNode, int destinationNode, IntersectionNode[] nodes) {
this.nodes = nodes;
this.s = sourceNode;
this.d = destinationNode;
initialize();
}
private void initialize() {
int k = this.d;
paths = new ArrayList<PathComponent>();
if(this.nodes[k].getDistanceTo() < Double.POSITIVE_INFINITY) {
stringPath = "";
while(k != this.s) {
int p = this.nodes[k].getPreceedingVertex();
totalWeight += this.nodes[k].getWeight();
stringPath = (this.nodes[p].isFuelStation() ? "(Refuelling Stop),\n" : "") +
String.format("%d -> %d", p, k)
+ (d == k ? "" : ",\n") + stringPath;
paths.add(0, new PathComponent(p, k));
k = p;
}
//pathSeries.add(0, s);
}
}
public double getRemainingDistance() {
return this.nodes[d].getRemainingDistance();
}
public double getDistanceTo() {
return this.nodes[d].getDistanceTo();
}
public List<PathComponent> getPathComponents() {
return this.paths;
}
public String getPath() {
return this.stringPath;
}
public int getSource() {
return this.s;
}
public int getDestination() {
return this.d;
}
public Double getTotalWeight() {
return this.totalWeight;
}
}
class GraphData {
private final int V;
private final double[][] adjacencyMatix;
public GraphData(int V, double[][] arrayMatrix) {
if (V < 0) throw new IllegalArgumentException("Vertices cannot be negative");
this.V = V;
this.adjacencyMatix = arrayMatrix;
}
public double[][] adjacencyMatix() {
return this.adjacencyMatix;
}
public int V() {
return this.V;
}
}
class Bag<Item> implements Iterable<Item> {
private int N; // number of elements in bag
private Node<Item> first; // beginning of bag
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
/**
* Initializes an empty bag.
*/
public Bag() {
first = null;
N = 0;
}
/**
* Is this bag empty?
* @return true if this bag is empty; false otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in this bag.
* @return the number of items in this bag
*/
public int size() {
return N;
}
/**
* Adds the item to this bag.
* @param item the item to add to this bag
*/
public void add(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
N++;
}
/**
* Returns an iterator that iterates over the items in the bag in arbitrary order.
* @return an iterator that iterates over the items in the bag in arbitrary order
*/
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
// an iterator, doesn't implement remove() since it's optional
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
public ListIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}
class EdgeWeightedDigraph {
private final int V;
private int E;
private Bag<DirectedEdge>[] adj;
private IntersectionNode[] nodes;
public EdgeWeightedDigraph(int V)
{
if (V < 0) throw new IllegalArgumentException("Number of vertices cannot be less than zero");
this.V = V;
this.E = 0;
this.adj = (Bag<DirectedEdge>[]) new Bag[V];
this.nodes = new IntersectionNode[V];
for(int i = 0; i < V; i++)
{
this.adj[i] = new Bag<DirectedEdge>();
//this.nodes[i] = new IntersectionNode(i);
}
}
public EdgeWeightedDigraph(GraphData adjacencyMatrix) {
this(adjacencyMatrix.V());//calls upper constructor
double[][] adjacencyList = adjacencyMatrix.adjacencyMatix();
for(int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++) {
double weight = adjacencyList[i][j];
if (weight > 0) {
DirectedEdge e = new DirectedEdge(i, j, weight);
addEdge(e);
}
}
}
}
private void addEdge(DirectedEdge e) {
int v = e.from(); //source
adj[v].add(e);
E++;
}
/**
*
* @return the number of vertices in the graph
*/
public int V() {
return this.V;
}
/**
*
* @return the number of edges in the graph
*/
public int E() {
return this.E;
}
public Iterable<DirectedEdge> adj(int v) {
if(v < 0 || v >= V) throw new IndexOutOfBoundsException("Vertex must be present in graph");
Bag<DirectedEdge> list = new Bag<DirectedEdge>();
for(DirectedEdge e : this.adj[v]) {
list.add(e);
}
return list;
}
public Iterable<DirectedEdge> edges()
{
Bag<DirectedEdge> list = new Bag<DirectedEdge>();
for(int v = 0; v < this.V; v++) {
for(DirectedEdge e : adj[v]) {
//System.out.println(e.toString());
list.add(e);
}
}
return list;
}
public int outdegree (int v)
{
if(v < 0 || v >= V) throw new IndexOutOfBoundsException("Vertice out of range");
return this.adj[v].size();
}
public void printEdges()
{
}
}
class MinPriorityQueue <Key extends Comparable<Key>>{
public Key[] keys;
public int[] pq;
public int[] qp;
private final int maxCapacity;
public int N;
public MinPriorityQueue(int capacity) {
keys = (Key[]) new Comparable[capacity];
pq = new int[capacity];
qp = new int[capacity];
maxCapacity = capacity;
for(int i = 0; i < capacity; i++) {
qp[i] = -1; pq[i] = -1;
}
}
public Boolean isEmpty() {
return this.N == 0;
}
public int extractMin() {
if(isEmpty()) {
throw new IllegalArgumentException("No Element Exists");
} else {
int minKeyIndex = pq[0];
int lastKeyIndex = pq[N-1];
if(N > 1) {
pq[0] = pq[N-1]; //increaseKey??
qp[lastKeyIndex] = 0;
pq[N-1] = -1;
} else
pq[0] = -1;
qp[minKeyIndex] = -1;
N--;
minHeapify(0);
return minKeyIndex;
}
}
public Key findMin() {
if(isEmpty()) {
return null;
} else
return keys[pq[0]];
}
/**
* Increase-Key
* @param key
* @param newObject
*/
public void insert(int key, Key newObject) {
if (key < 0 || key >= maxCapacity)
throw new IndexOutOfBoundsException();
pq[N] = key;
qp[key] = N;
keys[key] = newObject;
int loc = N;
while (loc > 0 && keys[pq[parent(loc)]].compareTo(keys[pq[loc]]) > 0) {
swap(parent(loc), loc);
loc = parent(loc);
}
N++;
}
/**
* O(1)
* Contains Key Value (Source Vertex)
* @param key
* @return
*/
public Boolean containsKey(int key) {
if(key < 0 || key >= maxCapacity)
return false;
//throw new IndexOutOfBoundsException();
return qp[key] != -1;
}
/**
* Checks if the node position is initialized.
*/
public Boolean nodeValueExists(int i) {
if(i < 0 || i >= maxCapacity)
{
//throw new IndexOutOfBoundsException();
return false;
}
return pq[i] != -1;
}
public void increaseKey(int key, Key newObject) {
if (containsKey(key)) {
if (keys[key].compareTo(newObject) <= 0) {
keys[key] = newObject;
int pIndex = qp[key];
minHeapify(pIndex);
}
}
}
/**
* O(lgn)
* @param key
* @param newObject
*/
public void decreaseKey(int key, Key newObject) {
if (containsKey(key)) {
if (keys[key].compareTo(newObject) > 0) {
keys[key] = newObject;
int pIndex = qp[key];
minHeapify(pIndex);
}
}
}
/**
* If current node < parent(current) : swap(parent,current)
* This function holds the min-heap property
* @param heap
* @param i index of key changed
*/
private <E extends Comparable<E>> void minHeapify(int i) {
int leftChild = leftChild(i);
int rightChild = rightChild(i);
int smallestChild = i;
if(nodeValueExists(leftChild) && keys[pq[leftChild]].compareTo(keys[pq[i]]) <= 0)
smallestChild = leftChild;
else if(nodeValueExists(rightChild) && keys[pq[rightChild]].compareTo(keys[pq[i]]) <= 0)
smallestChild = rightChild;
if(smallestChild != i) {
swap(i, smallestChild);
minHeapify(smallestChild);
}
}
private void swap(int i, int j) {
int targetObject = pq[i];
pq[i] = pq[j];
pq[j] = targetObject;
qp[pq[i]] = j;
qp[pq[j]] = i;
}
private int leftChild(int i) {
return 2*i + 1;
}
private int rightChild(int i) {
return 2*i + 2;
}
private int parent(int i) {
if((i + 1) == 1)
throw new IllegalArgumentException("root has no parent");
return ((i + 1) / 2) - 1;
}
}
class IntersectionNode {
private int v; //source vertex
private boolean isFuelingStation;
private DirectedEdge edgeFrom;
private double distanceTo;
private double distanceToEmpty = 9;
private double remainingDistance;
public IntersectionNode(int v, boolean isFuelStation) {
this.v = v;
this.distanceTo = Double.POSITIVE_INFINITY;
setFuelingStation(isFuelStation);
}
public void setFuelingStation(Boolean r) {
this.isFuelingStation = r;
if (this.isFuelingStation)
this.remainingDistance = this.distanceToEmpty;
else
this.remainingDistance = 0;
}
public double getDistanceTo() {
return this.distanceTo;
}
public double getRemainingDistance() {
return this.remainingDistance;
}
public void setRemainingDistance(double rd) {
if(this.isFuelingStation)
this.remainingDistance = this.distanceToEmpty;
else
this.remainingDistance = rd;
}
public void setDistanceTo(double d, DirectedEdge e) {
this.distanceTo = d;
this.edgeFrom = e;
}
public int getSourceVertex() {
return this.v;
}
public Boolean isParent() {
return this.edgeFrom == null;
}
public Boolean isFuelStation() {
return this.isFuelingStation;
}
public int getPreceedingVertex() {
if(isParent())
throw new IllegalArgumentException("parent has no preceeding edge");
return this.edgeFrom.from();
}
public double getWeight() {
if(isParent())
throw new IllegalArgumentException("parent has no preceeding edge");
return this.edgeFrom.weight();
}
public void setStartingNode() {
this.distanceTo = 0;
}
}
class DirectedEdge implements Comparable<DirectedEdge> {
private final int v;
private final int w;
private final double weight;
public DirectedEdge(int v, int w, double weight)
{
if (v < 0) throw new IndexOutOfBoundsException("Vertex names must be non-negative");
if (w < 0) throw new IndexOutOfBoundsException("Vertex names must be non-negative");
if (Double.isNaN(weight)) throw new IllegalArgumentException("Weight is NaN");
this.v = v;
this.w = w;
this.weight = weight;
}
public int from()
{
return this.v;
}
public char fromChar()
{
return (char)(this.v + 65);
}
public int to()
{
return this.w;
}
public char toChar()
{
return (char)(this.w + 65);
}
public double weight()
{
return this.weight;
}
public String toString()
{
return String.format("%s -> %s (%f)", this.fromChar(), this.toChar(), this.weight);
}
@Override
public int compareTo(DirectedEdge o) {
// TODO Auto-generated method stub
return this.weight < o.weight ? 0 : 1;
}
}
public class Main {
private static IntersectionNode[] distTo = null;
private static MinPriorityQueue<Double> Q;
private static int distanceToEmpty = 9;
private static int remainingDistance = 7;
private static int source = 0;
private static int destination = 4;
public static void DijkstraFunc(EdgeWeightedDigraph G, int s, int d, double remainingDistance, double distanceToEmpty, int[] fuelData)
{
int V = G.V();
if (s < 0 || s > V - 1)
throw new IllegalArgumentException(String.format("vertex(%d) does not exist in graph (source vertex)", s));
if (d < 0 || d > V - 1)
throw new IllegalArgumentException(String.format("vertex(%d) does not exist in graph (destination vertex)", s));
for(DirectedEdge e : G.edges()) { //E
if(e.weight() < 0)
throw new IllegalArgumentException(String.format("%d -> %d (%f) has a negative weight", e.from(), e.to(), e.weight()));
}
for(int i = 0; i < fuelData.length; i++) {
if (fuelData[i] < 0 || fuelData[i] > V - 1)
throw new IllegalArgumentException(String.format("vertex(%d) does not exist in graph (fuel station)", fuelData[i]));
}
//Attempt to find the shortest path(s->d) without traversing through a fuel-station, f(k), where k lies in 0 <= k < V
IntermediatePath path0 = findPath(G, s, d, remainingDistance, distanceToEmpty, fuelData);
System.out.format("weight(G) = %f", path0.getDistanceTo());
}
/**
* Form a graph (1) between s and every fuel stations, (2) between every fuel station and destination node
* We are creating another adjacency matrix, and we execute Dijsktra's modified algorithm on this graph to find shortest path (s->d)
* @param sourceGraph
* @param s
* @param d
* @param remainingDistance
* @param distanceToEmpty
* @param fuelStations
*/
private static IntermediatePath findPath(EdgeWeightedDigraph G, int s, int d, double remainingDistance, double distanceToEmpty, int[] fuelData) {
int V = G.V();
int P = 0;
int[] nFuelTable = new int[fuelData.length];
int[] translationTable;
double[][] adjacencyMatrix;
String[][] printMatrix;
initialize(s, fuelData, V);
for(int v = 0 ; v < V; v++) {
if(v == s || v == d || distTo[v].isFuelStation())
P++;
}
translationTable = new int[P];
adjacencyMatrix = new double[P][P];
printMatrix = new String[P][P];
int j = 0;
int f = 0;
for(int v = 0; v < V; v++) {
if(v == s || v == d || distTo[v].isFuelStation()) {
if(distTo[v].isFuelStation()) {
nFuelTable[f] = j;
f++;
}
//update s & d to the values in our new graph
if(v == s) s = j;
else if (v == d) d = j;
translationTable[j] = v;
j++;
}
}
/**
* O(V^2)
*
*
*/
for(int row = 0; row < P; row++) {
//no need to calculate shortest path from destination
for(int column = 0; column < P; column++) {
//shortest path from node to itself is 0
if(translationTable[row] == translationTable[column])
continue;
//String path0 = String.format("%d -> %d", translationTable[row], translationTable[column]);
//Note: remainingDistance applies to only source->f(k), if we are calculating f(k) to any other node, then we have distanceToEmpty, since "we are at fuel station node".
IntermediatePath path = Dijsktra(G, translationTable[row], translationTable[column], translationTable[row] == s ? remainingDistance : distanceToEmpty, distanceToEmpty, fuelData);
Double distanceTo = path.getDistanceTo();
if(distanceTo > 0 && path.getDistanceTo() <= Double.POSITIVE_INFINITY) { // <= distanceToEmpty ??
adjacencyMatrix[row][column] = path.getDistanceTo();
printMatrix[row][column] = path.getPath();
}
}
}
/**
* Form a graph(G) from (1) s to all fuel stations, (2) fuel stations to destination
* Run Dijsktra's algorithm one more time over this graph to find solution.
*/
GraphData mMatrix = new GraphData(translationTable.length, adjacencyMatrix);
EdgeWeightedDigraph mG = new EdgeWeightedDigraph(mMatrix);
//System.out.println(printMatrix[s][d]);
IntermediatePath path0 = Dijsktra(mG, s, d, remainingDistance, distanceToEmpty, nFuelTable);
//Since the graph formed is of mG
List<PathComponent> pathComponents = path0.getPathComponents();
for(int i = 0; i < pathComponents.size(); i++) {
System.out.println(printMatrix[pathComponents.get(i).getSource()][pathComponents.get(i).getDestination()]);
}
return path0;
}
private static void initialize(int s, int[] fuelData, int V) {
distTo = new IntersectionNode[V];
for(int v = 0; v < V; v++)
distTo[v] = new IntersectionNode(v, false);
distTo[s].setStartingNode();
distTo[s].setRemainingDistance(remainingDistance);
for(int i = 0; i < fuelData.length; i++) {
distTo[fuelData[i]].setFuelingStation(true);
}
}
/**
*
* @param G
* @param s (index) of source vertex
*/
public static IntermediatePath Dijsktra(EdgeWeightedDigraph G, int s, int d, double remainingDistance, double distanceToEmpty, int[] fuelData)
{
int V = G.V();
//0, 1, 2, 3, 4 are vertex nodes, the index (n) represents nth vertex
/**
* O(V)
*/
initialize(s, fuelData, V);
/**
* Initially, put the source node on the stack and initialize distance = 0.0 (so extractMin() selects vertex(s) first)
*/
Q = new MinPriorityQueue<Double>(V);
Q.insert(s, 0.0);
while(!Q.isEmpty()) {
int u = Q.extractMin(); // O(VlgV)
for(DirectedEdge e : G.adj(u)) { //O(E), aggregate analysis
relax(e);
}
}
return new IntermediatePath(s, d, distTo);
}
private static void relax(DirectedEdge e)
{
/**
* Edge e, represents the street edge from intersection(v) to intersection(w) with a weight of e.weight()
*/
int v = e.from();
int w = e.to();
/**
* The distance to the adjacent node = distanceTo (current node) + weight of the street edge
*/
double d = distTo[v].getDistanceTo() + e.weight(); //distance to adjacent node
/**
* r represents remaining distance from current node
* nr represents the remaining distance of adjacent node
* if nr >=0, adjacent node is reachable
*/
double r = distTo[v].getRemainingDistance();
double nr = r - e.weight();
/**
* Condition: relaxedDistance(adjacentNode) < existingDistance(adjacentNode) AND remainingDistance(currentNode) >= e.weight() (must be reachable)
*/
if(d < distTo[w].getDistanceTo() && nr >= 0) {
distTo[w].setDistanceTo(d, e);
distTo[w].setRemainingDistance(nr);
if (Q.containsKey(w))
Q.decreaseKey(w, d); //O(ElgV)
else
Q.insert(w, d); //O(ElgV)
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
boolean debugMode = false;
try {
if(debugMode == false) {
Scanner s = new Scanner(System.in);
System.out.println("Enter \"REMAINING_DISTANCE_TO_EMPTY\"");
remainingDistance = s.nextInt();
System.out.println("Enter \"DRIVING_RANGE_VEHICLE\"");
distanceToEmpty = s.nextInt();
System.out.println("Enter \"SOURCE NODE, (0...V-1), IT FOLLOWS 0-BASED INDEX\"");
source = s.nextInt();
System.out.println("Enter \"DESTINATION NODE, (0...V-1), IT FOLLOWS 0-BASED INDEX\"");
destination = s.nextInt();
s.close();
}
EdgeWeightedDigraph G = new EdgeWeightedDigraph(GraphUtility.readGraph());
DijkstraFunc(G, source, destination, remainingDistance, distanceToEmpty, GraphUtility.readFuelInfo());
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}