Created
December 10, 2019 22:57
-
-
Save aortiz49/2540547ff6d515d6249b947a642f9445 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// ------------------------------------------------------------- | |
// Point 10 | |
// ------------------------------------------------------------- | |
/** | |
* Creates a graph containing the uber zones as vertices. The edge cost are calculated in the | |
* following way: | |
* (1) From zoneA to zoneB there will only be one edge. | |
* (2) For any edge x, if it isn't in the hash table, find all trips in the csv file | |
* that match the respective start & end zones and take the average of their travel times. | |
* (3) For the same edge, find all trips in the csv file that match the respective start | |
* & end zones but in the reverse direction and take the average of their travel times. | |
* (4) Take the average of both of these trips. | |
* Additional notes: If an edge from the original graph is located inside the same zone, | |
* don't consider it for the zones graph. | |
*/ | |
public Graph<Integer, GraphVertex> createZoneGraph() { | |
zonesGraph = new Graph<>(5); | |
// hash tables to keep track of what has already added to the graph | |
HashTable<Integer, Integer> vertexMap = new HashTable<>(); | |
HashTable<String, Integer> edgeMap = new HashTable<>(); | |
// dynamic array that stores edges with no trips | |
DynamicArray<String> noUberTrips = new DynamicArray<>(); | |
// list of edges in the current graph | |
DynamicArray<Edge<Integer>> edgeList = graph.getMapEdgeList(); | |
// iterate over every edge | |
for (int i = 0; i < edgeList.size(); i++) { | |
// current vertices of the current edge | |
GraphVertex startVertex = graph.getVertexInfo(edgeList.get(i).getStartVertex()); | |
GraphVertex endVertex = graph.getVertexInfo(edgeList.get(i).getEndVertex()); | |
int startZone = startVertex.getZone(); | |
int endZone = endVertex.getZone(); | |
// go to next edge if the zones are the same | |
if (startZone != endZone) { | |
// comparison booleans for the latter decisions | |
boolean startVExists = vertexMap.containsKey(startZone); | |
boolean endVExists = vertexMap.containsKey(endZone); | |
boolean edgeExists = edgeMap.containsKey(startZone + "$" + endZone) && edgeMap | |
.containsKey(endZone + "$" + startZone); | |
// if start vertex isn't in the map (don't care about the value) | |
if (!startVExists) { | |
vertexMap.putNode(startZone, 0); | |
startVertex.setId(startZone); | |
zonesGraph.addVertex(startZone, startVertex); | |
} | |
// if end vertex isn't in the map (don't care about the value) | |
if (!endVExists) { | |
vertexMap.putNode(endZone, 0); | |
endVertex.setId(endZone); | |
zonesGraph.addVertex(endZone, endVertex); | |
} | |
// if the edge exists (A->B & B->A) | |
if (!edgeExists) { | |
// calculate the average of the bidirectional costs | |
double costAtoB = calculateCost2(startVertex, endVertex); | |
double costBtoA = calculateCost2(endVertex, startVertex); | |
// average of costs. (from A->B and B->A) | |
double newAvgTime = (costAtoB + costBtoA) / 2; | |
// if the avg is 100, that means there were no trips in either direction | |
// add this edge to the list of noTrips | |
if (newAvgTime == 100.0) { | |
newAvgTime = 200.0; | |
noUberTrips.add(startZone + "-" + endZone); | |
} | |
zonesGraph.addEdge(startZone, endZone, 0, newAvgTime, 0); | |
edgeMap.putNode(startZone + "$" + endZone, 0); | |
edgeMap.putNode(endZone + "$" + startZone, 0); | |
} | |
} | |
} | |
return zonesGraph; | |
} | |
public void drawZoneGraph(DynamicArray<Edge<Integer>> pEdges) { | |
DynamicArray<LatLng[]> edgeVerts = new DynamicArray<>(); | |
for (int i = 0; i < pEdges.size(); i++) { | |
int startId = pEdges.get(i).getStartVertex(); | |
int endId = pEdges.get(i).getEndVertex(); | |
GraphVertex startVertex = zonesGraph.getVertexInfo(startId); | |
GraphVertex endVertex = zonesGraph.getVertexInfo(endId); | |
double startLat = startVertex.getLatitude(); | |
double startLong = startVertex.getLongitude(); | |
double endLat = endVertex.getLatitude(); | |
double endLong = endVertex.getLongitude(); | |
LatLng start = new LatLng(startLat, startLong); | |
LatLng end = new LatLng(endLat, endLong); | |
LatLng[] locations = {start, end}; | |
edgeVerts.add(locations); | |
} | |
new Mapa("zones", edgeVerts); | |
} | |
public void drawPathGraph(DynamicArray<Edge<Integer>> pEdges) { | |
DynamicArray<LatLng[]> edgeVerts = new DynamicArray<>(); | |
for (int i = 0; i < pEdges.size(); i++) { | |
int startId = pEdges.get(i).getStartVertex(); | |
int endId = pEdges.get(i).getEndVertex(); | |
GraphVertex startVertex = graph.getVertexInfo(startId); | |
GraphVertex endVertex = graph.getVertexInfo(endId); | |
double startLat = startVertex.getLatitude(); | |
double startLong = startVertex.getLongitude(); | |
double endLat = endVertex.getLatitude(); | |
double endLong = endVertex.getLongitude(); | |
LatLng start = new LatLng(startLat, startLong); | |
LatLng end = new LatLng(endLat, endLong); | |
LatLng[] locations = {start, end}; | |
edgeVerts.add(locations); | |
} | |
Mapa map = new Mapa("zones", edgeVerts); | |
} | |
public void drawPath1Graph(DynamicArray<Integer> pVerts) { | |
DynamicArray<LatLng[]> edgeVerts = new DynamicArray<>(); | |
for (int i = pVerts.size() - 1; i > 0; i--) { | |
Edge<Integer> edge = new Edge<>(pVerts.get(i), pVerts.get(i - 1), 0, 0, 0); | |
int startId = edge.getStartVertex(); | |
int endId = edge.getEndVertex(); | |
GraphVertex startVertex = graph.getVertexInfo(startId); | |
GraphVertex endVertex = graph.getVertexInfo(endId); | |
double startLat = startVertex.getLatitude(); | |
double startLong = startVertex.getLongitude(); | |
double endLat = endVertex.getLatitude(); | |
double endLong = endVertex.getLongitude(); | |
LatLng start = new LatLng(startLat, startLong); | |
LatLng end = new LatLng(endLat, endLong); | |
LatLng[] locations = {start, end}; | |
edgeVerts.add(locations); | |
} | |
new Mapa("zones", edgeVerts); | |
} | |
/** | |
* Returns the zone graph | |
* | |
* @return the zone graph | |
*/ | |
public Graph<Integer, GraphVertex> getZoneGraph() { | |
return zonesGraph; | |
} | |
/** | |
* Returns the graph | |
* | |
* @return the graph | |
*/ | |
public Graph<Integer, GraphVertex> getGraph() { | |
return graph; | |
} | |
// ------------------------------------------------------------- | |
// Point 11 | |
// ------------------------------------------------------------- | |
public DynamicArray<Integer> minPath(int pStartVertex, int pEndVertex) { | |
// if the zone graph is loaded, there are fewer vertices in that graph than there are | |
// total possible zones. So, add an offset to the size to prevent a null pointer exception. | |
int diff = Math.abs(graph.getVertices() - maxZoneId) + 1; | |
DynamicArray<Double> distTo = new DynamicArray<>(graph.getVertices() + diff); | |
DynamicArray<Integer> vertexFrom = new DynamicArray<>(graph.getVertices() + diff); | |
LinkedList<Integer, Integer> queue = new LinkedList<>(); | |
for (int i = 0; i < graph.getVertices(); i++) { | |
distTo.add(Double.POSITIVE_INFINITY); | |
} | |
graph.uncheckAll(); | |
VertexNode<Integer, GraphVertex> start = graph.getVertexNode(pStartVertex); | |
start.setVisited(); | |
vertexFrom.set(pStartVertex, -1); | |
distTo.set(pStartVertex, 0.0); | |
queue.append(new Node<>(pStartVertex, 0)); | |
while (!queue.isEmpty()) { | |
Node<Integer, Integer> curr = queue.removeHead(); | |
VertexNode<Integer, GraphVertex> currVertex = graph.getVertexNode(curr.getId()); | |
DynamicArray<Node<Integer, Double[]>> adjacentVertices = | |
currVertex.getAdjacentVerticesList(); | |
// iterate over adjacent vertices | |
for (int i = 0; i < adjacentVertices.size(); i++) { | |
int currId = adjacentVertices.get(i).getId(); | |
VertexNode<Integer, GraphVertex> currAdj = graph.getVertexNode(currId); | |
if (!currAdj.isVisited()) { | |
currAdj.setVisited(); | |
vertexFrom.set(currId, curr.getId()); | |
distTo.set(currId, distTo.get(curr.getId()) + 1); | |
queue.append(new Node<>(currAdj.getId(), 0)); | |
} | |
} | |
} | |
DynamicArray<Integer> fromList = new DynamicArray<>(); | |
Integer startP = vertexFrom.get(pEndVertex); | |
if (startP != null) { | |
fromList.add(pEndVertex); | |
int curr = startP; | |
while (curr != -1) { | |
fromList.add(curr); | |
curr = vertexFrom.get(curr); | |
} | |
} | |
return fromList; | |
} | |
/** | |
* Returns the longest path out of the shortest possible paths from a vertex to any of its | |
* reachable vertices | |
* | |
* @param pStartZone the start zone | |
* @return | |
*/ | |
public DynamicArray<Edge<Integer>> longestReachablePath(int pStartZone) { | |
DynamicArray<Edge<Integer>> edges = new DynamicArray<>(); | |
// queue to store the paths | |
PriorityQueue<QueueNode<Integer, DynamicArray<Integer>>> pathsQueue = new PriorityQueue<>(); | |
// reachable vertices | |
DynamicArray<Integer> reachableVertices = graph.getReachableVertices(pStartZone); | |
// iterate over all reachable vertices | |
for (int i = 0; i < reachableVertices.size(); i++) { | |
int end = reachableVertices.get(i); | |
DynamicArray<Integer> path = minPath(pStartZone, end); | |
int cost = path.size() - 1; | |
pathsQueue.add(new QueueNode<>(cost, path), false); | |
} | |
if (pathsQueue.size() != 0) { | |
DynamicArray<Integer> maxPath = pathsQueue.delMax().getValue(); | |
for (int i = maxPath.size() - 1; i > 0; i--) { | |
int start = graph.getVertexNode(maxPath.get(i)).getValue().getId(); | |
int end = graph.getVertexNode(maxPath.get(i - 1)).getValue().getId(); | |
Edge<Integer> edge = new Edge<>(start, end, 0, 0, 0); | |
edges.add(edge); | |
} | |
} | |
return edges; | |
} | |
// ------------------------------------------------------------- | |
// Point 12 | |
// ------------------------------------------------------------- | |
public DynamicArray<Integer> djikstra(int pStartVertex, int pEndVertex) { | |
// if the zone graph is loaded, there are fewer vertices in that graph than there are | |
// total possible zones. So, add an offset to the size to prevent a null pointer exception. | |
totalCost = 0; | |
int diff = Math.abs(graph.getVertices() - maxZoneId) + 1; | |
DynamicArray<Double> distTo = new DynamicArray<>(graph.getVertices() * 2 + diff); | |
DynamicArray<Integer> vertexFrom = new DynamicArray<>(graph.getVertices() + diff); | |
IndexPQ<QueueNode2<Double, Integer>> queue = new IndexPQ<>(graph.getVertices() + diff); | |
// keep track of the added vertices | |
HashTable<Integer, Integer> vertexTable = new HashTable<>(); | |
// Set distTo to infinity for all vertices | |
for (int i = 0; i < graph.getVertices() * 2 + diff; i++) { | |
distTo.add(Double.POSITIVE_INFINITY); | |
} | |
// uncheck all as visited just in case we already executed it earlier | |
graph.uncheckAll(); | |
VertexNode<Integer, GraphVertex> start = graph.getVertexNode(pStartVertex); | |
vertexFrom.set(pStartVertex, -1); | |
distTo.set(pStartVertex, 0.0); | |
queue.insert(pStartVertex, new QueueNode2<>(distTo.get(pStartVertex), pStartVertex)); | |
int test = 0; | |
while (!queue.isEmpty()) { | |
int curr = queue.delMin(); | |
VertexNode<Integer, GraphVertex> currVertex = graph.getVertexNode(curr); | |
currVertex.setVisited(); | |
DynamicArray<Node<Integer, Double[]>> adjacentVertices = | |
currVertex.getAdjacentVerticesList(); | |
int test1 = 0; | |
// iterate over adjacent vertices | |
for (int i = 0; i < adjacentVertices.size(); i++) { | |
Node<Integer, Double[]> currNode = adjacentVertices.get(i); | |
int currId = currNode.getId(); | |
double prevWeight = distTo.get(currId); | |
// calculate distance to father plus distance to child | |
double currWeight = distTo.get(curr) + currNode.getValue()[1]; | |
VertexNode<Integer, GraphVertex> currAdj = graph.getVertexNode(currId); | |
if (!currAdj.isVisited()) { | |
if (prevWeight > currWeight) { | |
distTo.set(currId, currWeight); | |
vertexFrom.set(currId, curr); | |
if (queue.contains(currId)) { | |
queue.decreaseKey(currId, new QueueNode2<>(currWeight, currId)); | |
} | |
else | |
queue.insert(currId, new QueueNode2<>(currWeight, currId)); | |
} | |
// keep track if it exists or not | |
vertexTable.putNode(currAdj.getId(), 0); | |
} | |
} | |
} | |
DynamicArray<Integer> fromList = new DynamicArray<>(); | |
Integer startP = vertexFrom.get(pEndVertex); | |
if (startP != null) { | |
fromList.add(pEndVertex); | |
int curr = startP; | |
while (curr != -1) { | |
fromList.add(curr); | |
curr = vertexFrom.get(curr); | |
} | |
} | |
for (int i = 1; i < fromList.size(); i++) { | |
totalCost +=distTo.get(fromList.get(i)); | |
} | |
return fromList; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment