Came across this question recently, thought it was interesting.

**Problem:**

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.

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 max 4 stops.

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: 4

Output #8: 9

Output #9: 9

Output #10: 7

**SOLUTION**

Before we jump to coding this, let’s think of the problem, identify the data structures that could/should be used, define some of the presented elements in a more concrete fashion, then go from there.

Obviously, the main data structure here is going to be a directed, and weighted graph. The two most common ways to implement this would be an adjacency matrix and an adjacency list. Take a quick glance at the graph that is presented to us. It isn’t very complete, so for this particular problem, the the adjacency matrix would be iterating over a lot of empty cells at O(|V|^2) time. So for a sparse graph like this one, an adjacency list is better in terms of both, space and lookup/traversal times. Traversal in the adjacency list could be done at O(|V| + |E|) time, where V = # of Vertices, and E = # of edges.

A vertex, or a node here could be the city. And the edge could be the path between the two cities, with the distance. The graph then, could be a hash table with all the nodes as keys, each of which points towards a chained list of possible edges. Each edge could have a “from” node and a “to” node. That is basically it. This is what we’ve got so far, then.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
package com.utsavized.trains; public 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(); } } |

Notice that since you will be using your own class as a key, the default equals() or contains() functions wont work. In Java, the contains() function will first look up for the hashCode(), and only then, if it needs to will look up the equals() function. Although even in any other case, always good to override hashCode() when you override equals(). I didn’t add a toString() function, but it is considered good practice to override that as well.

Next is our edge.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
package com.utsavized.trains; public 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; } } |

And finally, this is part of the graph:

1 2 3 4 5 6 7 8 9 10 |
package com.utsavized.trains; import java.util.ArrayList; import java.util.Hashtable; public class Routes { public Hashtable<Node, Edge> routeTable; public Routes() { this.routeTable = new Hashtable<Node, Edge>(); } ... |

Now according to this programming challenge, we need to be able to perform four different functions on the graph: Find distance of an explicitly defined route, Find the number of possible routes between two nodes given the maximum number of edges (as in stops), Find the shortest route between two nodes, and Find all possible routes (even repeating) from one node to another, given the maximum distance (or weight).

So here is the complete graph class with all the methods as well.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 |
package com.utsavized.trains; import java.util.ArrayList; import java.util.Hashtable; public 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; } } |

Finally, here are the JUnit tests to run (as per the requirements of the question).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
package com.utsavized.trains; import static org.junit.Assert.*; import java.util.ArrayList; import org.junit.BeforeClass; import org.junit.Test; public class TrainsTest { static Routes graph; static Node a, b, c, d, e; @BeforeClass public static 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)); } @Test public void testDistanceBetween_ABC() throws Exception { ArrayList<Node> route = new ArrayList<Node>(); route.add(a); route.add(b); route.add(c); assertEquals(9, graph.distanceBetween(route)); } @Test public void testDistanceBetween_AD() throws Exception { ArrayList<Node> route = new ArrayList<Node>(); route.add(a); route.add(d); assertEquals(5, graph.distanceBetween(route)); } @Test public void testDistanceBetween_ADC() throws Exception { ArrayList<Node> route = new ArrayList<Node>(); route.add(a); route.add(d); route.add(c); assertEquals(13, graph.distanceBetween(route)); } @Test 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); assertEquals(22, graph.distanceBetween(route)); } @Test(expected=Exception.class) public void testDistanceBetween_AED() throws Exception { ArrayList<Node> route = new ArrayList<Node>(); route.add(a); route.add(e); route.add(d); assertEquals(-1, graph.distanceBetween(route)); } @Test public void testNumStops_CC3() throws Exception { int numStops = graph.numStops(c, c, 3); assertEquals(2, numStops); } @Test public void testNumStops_AC4() throws Exception { int numStops = graph.numStops(a, c, 4); assertEquals(4, numStops); } @Test public void testShortestRoute_AC() throws Exception { int shortestRoute = graph.shortestRoute(a, c); assertEquals(9, shortestRoute); } @Test public void testShortestRoute_BB() throws Exception { int shortestRoute = graph.shortestRoute(b, b); assertEquals(9, shortestRoute); } @Test public void numRoutesWithin_CC30() throws Exception { int numRoutesWithin = graph.numRoutesWithin(c, c, 30); assertEquals(7, numRoutesWithin); } @Test public void testEquals() { Node a1 = new Node("A"); Node a2 = new Node("A"); Node b = new Node("B"); assertEquals(true, a1.equals(a2)); assertEquals(false, a1.equals(b)); assertEquals(true, (new Node("Test").equals(new Node("Test")))); } } |

And yes, they all pass. 🙂

** Final thoughts:**

The traversal can and should be optimized — I did a very straightforward version that came to my mind.

It is a good idea to encapsulate all the properties of your classes through some accessors and modifiers.

## Blog Comments

Anonymous

November 1, 2014 at 6:02 am

this is very good

Anonymous

August 5, 2015 at 11:45 pm

I’m finding it difficult to understand the question, Can you explain the same please?

Sree

September 15, 2016 at 2:43 am

Well designed, well developed and well explained!! Thank you very much! 🙂