Finding the minimum cycle path in a dynamically directed graph

Question

I recently came across this (Edit: Problem A) interesting problem from Spotify's hacker challenge earlier this year which involves determining the switching at train truck junctions to route a train back to it's starting point. The train must arrive facing the same direction it left and the train can never reverse on the tracks.

As I understand it, the problem can be modeled as an undirected(?) graph where we must find the shortest cycle from a certain vertex, or detect that no such cycle exists. However, the interesting part is that for a vertex, v, the vertices adjacent to v are dependent on the path taken to v, so in a sense the graph could be considered directed, though this direction is path-dependent.

My first thought was to model each node as 3 separate vertices, A, B and C, where A <-> B and A <-> C, and then use a breadth-first search to build a search tree until we find the original vertex, but this is complicated by the caveat above, namely that the adjacencies for a given vertex depend on the previous vertex we visited. This means that in our BFS tree, nodes can have multiple parents.

Obviously a simple BFS search won't be sufficient to solve this problem. I know there are algorithms that exist to detect cycles in a graph. One approach might be to detect all the cycles, then for each cycle, detect whether the path is valid. (i.e., does not reverse direction)

Does anyone else have any insights on approaches to solving this problem?

UPDATE: I followed the approach suggested by @Karussell in the comments.

Here is my solution on github.

The trick was to model the situation using an edge-based graph, not a traditional vertex-based graph. The input file supplied in the contest is conveniently specified in terms of edges already, so this file can be easily used to build an edge-based graph.

The program uses two important classes: Road and Solver. A Road has two integer fields, j1 and j2. j1 represents the source junction and j2 represents the target junction. Each road is one-way, meaning that you can only travel from j1 to j2. Each Road also includes a LinkedList of adjacent Roads and a parent Road. The Road class also includes static methods to convert between the Strings used in the input file and integer indexes representing the A, B, and C points at each junction.

For each entry in the input file, we add two Roads to a HashMap, one Road for each direction between the two junctions. We now have a list of all of the Roads that run between junctions. We just need to connect the roads together at the junctions through the A, B and C switches. If a Road ends at Junction.A, we look up the roads that begin at Junction.B and Junction.C and add these roads as adjacencies. The buildGraph() function returns the Road whose target junction (j2) is "1A" == index 0.

At this point, our graph is constructed. To find the shortest path I simply used a BFS to traverse the graph. We leave the root unmarked and begin by queueing the root's adjacencies. If we find a road whose target junction is "1A" (index 0) then we have found the shortest cycle through the starting point. Once we reconstruct the path using each Road's parent property, it's a trivial matter to set the switches appropriately as required in the problem.

Thanks to Karussell for suggesting this approach. If you want to put your comment in answer form with a short explanation, I will accept it. Thanks to @Origin, as well. I must admit that I did not fully follow the logic of your answer, but that is certainly not to say that it is not correct. If anyone solves this problem using your solution, I would be very interested to see it.

Answer 1

As my comment suggested: I think that you can solve this via edge based graph or via an improvement which is more or less an 'enhanced' node based graph.

Details:

• Your situation is similar to turn restrictions in road networks. Those can be modeled if you create one node per (directed!) street and connect that nodes depending on the allowed turns.
• So, do not only store the position of your current position but also the direction and possible further 'situations'. To make it possible that even the same position with a 180° turn is different to your current state.

Instead of modeling your 'state' (which is directed!) into the graph you could also assign possible outcomes to every junction - now the algorithm needs to be more clever and needs to decide per junction what to do depending on your earlier state (including direction). I think, this is the main idea of the 'enhanced' node based graph which should be less memory intensive (not that important in your case).

Answer 2

One possible approach: first constract some kind of graph to model all connections (graph G). Then construct another graph in which we will find the cycle (graph H). For each node A in G, we will add a node to graph H. Each A node also has 2 outgoing edges (to the B and C nodes in graph G). In H, these edges will go to the next A node that would be encountered in G. For example, the A node in H corresponding to the A node of the switch with ID 3 would have an outgoing edge to node 9 and node 6 in H. The weight of each edge is the number of switches passed on that route (including the starting switch).

This will yield a graph in which we can grow a forward shortest path tree. If we would reach the start again, the cycle would be complete.

The key is that a switch is only a decision point if it is traversed in the A-> direction. It is not necessary to model the backward direction as this would only complicate the search.

edit: some more clarification

The problem consists of determining the shortest path from A to A (again). The definition of shortest is here the number of switches passed. This will be used in a Dijkstra based search algorithm. We basically are going to do Dijkstra on a graph H in which the cost of the edges is equal to the number of switches in that edge.

In the H graph, we will have a node for each switch. Each node will have 2 outgoing edges, corresponding to the 2 paths one can take (B and C directions). The edges in H will correspond to an entire route between 2 A nodes in the original graph. For the example in the problem description, we get the following:

A node corresponding to switch 1:

• 1 outgoing link to node 2, weight 2, corresponding to taking the C direction when leaving switch 1. The weight is 2 because we pass switch 1 and switch 3 if we go from A1->C1->C3->A3->A2
• 1 outgoing link to node 3, weight 2, corresponding to taking the B direction

A node corresponding to switch 2:

• 1 outgoing link to node 6, weight 2, corresponding to taking the B direction
• no second link as the C direction is a dead end

A node corresponding to switch 3:

• 1 outgoing link to node 6, weight 2, corresponding to taking the C direction
• 1 outgoing link to node 9, weight 3, corresponding to taking the B direction and passing switches 3, 7 and 8

and so on for every switch. This yield a graph with 10 nodes, each having at most 2 directed edges.

Now we can start building our Dijkstra tree. We start at node 1 and have 2 possible directions, B and C. We put those on a priorityqueue. The queue then contains [node 2,weight 2] and [node 3, weight 2] as we can reach the A entrance of switch 2 after passing 2 switches and the A entrance of switch 3 after passing 2 switches. We then continue the search by taking the lowest weight entry from the queue:

• [node 2, weight 2]: only the B direction to take, so put [node 6, weight 4] on the queue
• [node 3, weight 2]: 2 directions to take, so add [node 6, weight 4] and [node 9, weight 5] to the queue.
• [node 6, weight 4]: 2 directions possible, add [node 4, weight 5] and [node 8, weight 8] to the queue]
• [node 9, weight 5]: only the C direction, add [node 10, weight 6]
• [node 4, weight 5]: add [node 5, weight 7] for the C direction and [node 1, weight 9] for the B direction]
• [node 10, weight 6]:add [node 1, weight 8] for the C direction and [node 1, weight 10] for the B direction
• [node 5, weight 7]:add [node 1, weight 11] and [node 8, weight 10]
• [node 8, weight 8]: add [node 7, weight 9]
• [node 1, weight 8]: we found our way back so we can stop

(mistakes are possible, I'm just doing this by hand)

The algorithm then stops with a final length of 8 for a cycle. Determining the followed path is then just a matter of maintaining parent pointers for the nodes when you settle them and unpack the path.

We can use Dijkstra because each node in H corresponds to traversing an original node (in G) in the right direction. Each node in H can then be settled in a Dijkstra fashion so the complexity of the algorithm is limited to that of Dijkstra (which can handle the 100k upper limit for the number of switches).