The local commuter railroad services a number of towns in Kiwiland. Because of m
ID: 3570700 • Letter: T
Question
The local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are 'one-way.' That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance! The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.
Input: A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town. Output: For test input 1 through 5, if no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).
1. The distance of the route A-B-C.
2. The distance of the route A-D.
3. The distance of the route A-D-C.
4. The distance of the route A-E-B-C-D.
5. The distance of the route A-E-D.
6. The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
7. The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
8. The length of the shortest route (in terms of distance to travel) from A to C.
9. The length of the shortest route (in terms of distance to travel) from B to B.
10. The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.
Test Input: For the test input, the towns are named using the first few letters of the alphabet from A to E. A route between two towns (A to B) with a distance of 5 is represented as AB5. Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7
Expected Output: Output #1: 9 Output #2: 5 Output #3: 13 Output #4: 22 Output #5: NO SUCH ROUTE Output #6: 2 Output #7: 3 Output #8: 9 Output #9: 9 Output #10: 7
Explanation / Answer
// Program URL : http://ideone.com/L88M4t
import java.util.ArrayList;
import java.util.Hashtable;
class Node {
public String name;
public boolean visited;
public Node(String name) {
this.name = name;
this.visited = false;
}
@Override
public boolean equals(Object b) {
if (b == null || b.getClass() != getClass()) {
return false;
}
Node bx = (Node)b;
return this.name.equals(bx.name);
}
@Override
public int hashCode() {
if(this.name == null) return 0;
return this.name.hashCode();
}
}
class Edge {
//Name of origin town
public Node origin;
//Name of destination town
public Node destination;
//Route weight to destination
public int weight;
//next possible route
public Edge next;
//constructor
public Edge(Node origin, Node destination, int weight) {
this.origin = origin;
this.destination = destination;
this.weight = weight;
this.next = null;
}
public Edge next(Edge edge) {
this.next = edge;
return this;
}
}
class Routes {
public Hashtable<Node, Edge> routeTable;
public Routes() {
this.routeTable = new Hashtable<Node, Edge>();
}
/*
* Calculates the distance of a specific path
*/
public int distanceBetween(ArrayList<Node> cities) throws Exception {
/*There is no distance between
* no cities or 1 city*/
if(cities.size() < 2)
return 0;
int distance, depth, i;
distance = depth = i = 0;
/* For each city in the list,
* we check if entry exists in our
* hash table.
*/
while(i < cities.size() - 1) {
if(this.routeTable.containsKey(cities.get(i))) {
Edge route = this.routeTable.get(cities.get(i));
/*If key exists, we check if route from key to next
* city exists. We add the distance, and maintain a
* depth count
*/
while(route != null) {
if(route.destination.equals(cities.get(i + 1))) {
distance += route.weight;
depth++;
break;
}
route = route.next;
}
}
else
throw new Exception("NO SUCH ROUTE");
i++;
}
/*If edge depth is not equal to vertex - 1,
* then it is safe to assume that one ore more
* routes do not exist
*/
if(depth != cities.size() - 1)
throw new Exception("NO SUCH ROUTE");
return distance;
}
/*
* Number of stops;
* Wrapper for recursive function
*/
public int numStops(Node start, Node end, int maxStops) throws Exception{
//Wrapper to maintain depth of traversal
return findRoutes(start, end, 0, maxStops);
}
/*
* Finds number of stops from start to end,
* with a maximum of maxStops and the depth
* limit.
*/
private int findRoutes(Node start, Node end, int depth, int maxStops) throws Exception{
int routes = 0;
//Check if start and end nodes exists in route table
if(this.routeTable.containsKey(start) && this.routeTable.containsKey(end)) {
/*
* If start node exists then traverse all possible
* routes and for each, check if it is destination
* If destination, and number of stops within
* allowed limits, count it as possible route.
*/
depth++;
if(depth > maxStops) //Check if depth level is within limits
return 0;
start.visited = true; //Mark start node as visited
Edge edge = this.routeTable.get(start);
while(edge != null) {
/* If destination matches, we increment route
* count, then continue to next node at same depth
*/
if(edge.destination.equals(end)) {
routes++;
edge = edge.next;
continue;
}
/* If destination does not match, and
* destination node has not yet been visited,
* we recursively traverse destination node
*/
else if(!edge.destination.visited) {
routes += findRoutes(edge.destination, end, depth, maxStops);
depth--;
}
edge = edge.next;
}
}
else
throw new Exception("NO SUCH ROUTE");
/*
* Before exiting this recursive stack level,
* we mark the start node as visited.
*/
start.visited = false;
return routes;
}
/*
* Shortest route;
* Wrapper for recursive function
*/
public int shortestRoute(Node start, Node end) throws Exception {
//Wrapper to maintain weight
return findShortestRoute(start, end, 0, 0);
}
/*
* Finds the shortest route between two nodes
*/
private int findShortestRoute(Node start, Node end, int weight, int shortestRoute) throws Exception{
//Check if start and end nodes exists in route table
if(this.routeTable.containsKey(start) && this.routeTable.containsKey(end)) {
/*
* If start node exists then traverse all possible
* routes and for each, check if it is destination
*/
start.visited = true; //Mark start node as visited
Edge edge = this.routeTable.get(start);
while(edge != null) {
//If node not already visited, or is the destination, increment weight
if(edge.destination == end || !edge.destination.visited)
weight += edge.weight;
/* If destination matches, we compare
* weight of this route to shortest route
* so far, and make appropriate switch
*/
if(edge.destination.equals(end)) {
if(shortestRoute == 0 || weight < shortestRoute)
shortestRoute = weight;
start.visited = false;
return shortestRoute; //Unvisit node and return shortest route
}
/* If destination does not match, and
* destination node has not yet been visited,
* we recursively traverse destination node
*/
else if(!edge.destination.visited) {
shortestRoute = findShortestRoute(edge.destination, end, weight, shortestRoute);
//Decrement weight as we backtrack
weight -= edge.weight;
}
edge = edge.next;
}
}
else
throw new Exception("NO SUCH ROUTE");
/*
* Before exiting this recursive stack level,
* we mark the start node as visited.
*/
start.visited = false;
return shortestRoute;
}
/*
* Shortest route;
* Wrapper for recursive function
*/
public int numRoutesWithin(Node start, Node end, int maxDistance) throws Exception {
//Wrapper to maintain weight
return findnumRoutesWithin(start, end, 0, maxDistance);
}
/*
* Finds the shortest route between two nodes
*/
private int findnumRoutesWithin(Node start, Node end, int weight, int maxDistance) throws Exception{
int routes = 0;
//Check if start and end nodes exists in route table
if(this.routeTable.containsKey(start) && this.routeTable.containsKey(end)) {
/*
* If start node exists then traverse all possible
* routes and for each, check if it is destination
*/
Edge edge = this.routeTable.get(start);
while(edge != null) {
weight += edge.weight;
/* If distance is under max, keep traversing
* even if match is found until distance is > max
*/
if(weight <= maxDistance) {
if(edge.destination.equals(end)) {
routes++;
routes += findnumRoutesWithin(edge.destination, end, weight, maxDistance);
edge = edge.next;
continue;
}
else {
routes += findnumRoutesWithin(edge.destination, end, weight, maxDistance);
weight -= edge.weight; //Decrement weight as we backtrack
}
}
else
weight -= edge.weight;
edge = edge.next;
}
}
else
throw new Exception("NO SUCH ROUTE");
return routes;
}
}
public class TrainsTest {
static Routes graph;
static Node a, b, c, d, e;
public static void main(String args[]) {
TrainsTest t=new TrainsTest();
}
TrainsTest() {
try{ setUpBeforeClass();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testDistanceBetween_ABC();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testDistanceBetween_AD();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testDistanceBetween_ADC();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testDistanceBetween_AEBCD();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testDistanceBetween_AEBCD();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testDistanceBetween_AED();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testNumStops_CC3();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testNumStops_AC4();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testShortestRoute_AC();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ testShortestRoute_BB();}
catch(Exception e){System.out.println("Error="+e.toString());}
try{ numRoutesWithin_CC30();}
catch(Exception e){System.out.println("Error="+e.toString());}
/*try{ testEquals();}
catch(Exception e){System.out.println("Error="+e.toString());}*/
}
public void setUpBeforeClass() throws Exception {
graph = new Routes(); //Build graph
a = new Node("A");
b = new Node("B");
c = new Node("C");
d = new Node("D");
e = new Node("E");
/*Input given in programming challenge
Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7*/
graph.routeTable.put(a, new Edge(a, b, 5).next(new Edge(a, d, 5).next(new Edge(a, e, 7))));
graph.routeTable.put(b, new Edge(b, c, 4));
graph.routeTable.put(c, new Edge(c, d, 8).next(new Edge(c, e, 2)));
graph.routeTable.put(d, new Edge(d, c, 8).next(new Edge(d, e, 6)));
graph.routeTable.put(e, new Edge(e, b, 3));
}
public void testDistanceBetween_ABC() throws Exception {
ArrayList<Node> route = new ArrayList<Node>();
route.add(a);
route.add(b);
route.add(c);
System.out.println(9+"="+graph.distanceBetween(route));
}
public void testDistanceBetween_AD() throws Exception {
ArrayList<Node> route = new ArrayList<Node>();
route.add(a);
route.add(d);
System.out.println(5+"="+graph.distanceBetween(route));
}
public void testDistanceBetween_ADC() throws Exception {
ArrayList<Node> route = new ArrayList<Node>();
route.add(a);
route.add(d);
route.add(c);
System.out.println(13+"="+graph.distanceBetween(route));
}
public void testDistanceBetween_AEBCD() throws Exception {
ArrayList<Node> route = new ArrayList<Node>();
route.add(a);
route.add(e);
route.add(b);
route.add(c);
route.add(d);
System.out.println(22+"="+graph.distanceBetween(route));
}
public void testDistanceBetween_AED() throws Exception {
ArrayList<Node> route = new ArrayList<Node>();
route.add(a);
route.add(e);
route.add(d);
System.out.println(-1+"="+graph.distanceBetween(route));
}
public void testNumStops_CC3() throws Exception {
int numStops = graph.numStops(c, c, 3);
System.out.println(2+"="+numStops);
}
public void testNumStops_AC4() throws Exception {
int numStops = graph.numStops(a, c, 4);
System.out.println(4+"="+numStops);
}
public void testShortestRoute_AC() throws Exception {
int shortestRoute = graph.shortestRoute(a, c);
System.out.println(9+"="+shortestRoute);
}
public void testShortestRoute_BB() throws Exception {
int shortestRoute = graph.shortestRoute(b, b);
System.out.println(9+"="+shortestRoute);
}
public void numRoutesWithin_CC30() throws Exception {
int numRoutesWithin = graph.numRoutesWithin(c, c, 30);
System.out.println(7+"="+numRoutesWithin);
}
public void testEquals() throws Exception {
Node a1 = new Node("A");
Node a2 = new Node("A");
Node b = new Node("B");
System.out.println(true+"="+a1.equals(a2));
System.out.println(false+"="+a1.equals(b));
System.out.println(true+"="+(new Node("Test").equals(new Node("Test"))));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.