Graph Traversal and Such

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.

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.

And finally, this is part of the graph:

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.

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

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.

Tags:
Blog Comments

this is very good

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

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

Leave a Comment