Railway station task

A rail network is composed of a set of stations and the trakcs between them. In every station a specific good is unloaded from the cargo train. After that, the train is loaded with a new good and it leaves the station to go to the next one of its path.

The goal of the task is to find all the possible types of goods a cargo can be carrying when entering a station.

The algorithm

The algorithm keeps track of both the entry and leaving configurations for each station.

The possible objects present on a train when arriving at station s are IN(s) = \bigcup_{p \in pred(s)} OUT(p), where OUT(s) is defined as (IN(s) \setminus {unload(s)}) \cup {load(s)}

It follows a worklist based approach:

1. Set for every station IN(s)=OUT(s)=\emptyset
2. Add the initial station to the worklist
3. Pop a station, let it be s. Evaluate IN(s) and OUT(s)
4. If OUT(s) has changed then add all succ(s) to the worklist to propagate those new results
5. Continue until no more stations are in the worklist

The code

Two classes Railroad and Station were created to easily manage the computation, instances of both are generated from RailroadBuilder that parses the input. The actual computation of possible configurations is executed by CargoEvaluator.

The code is mostly a direct translation from the pseudocode given before to Kotlin. The IN and OUT are stored in a MutableMap<Int, Set<Int>>, maps of the configs indexed by station ids. To avoid unnecessary iteration if a station OUT changes and one of its successors is already in the worklist, it is not added again.

Test cases

To test the program some input files were defined following the specification provided. The proposed rail networks should cover some tricky cases in order to check the behaviour of the algorithm. A test suite is implemented in test/CargoEvaluatorTest.kt

The graphs are presented here. On every edge, representing the track that connect stations, a label indicates all the possible goods that can enter in that station through a cargo train from that predecessor station, the IN(s) in the pseudocode.

Direct path

Direct Graph

Basic configuration just to test the algorithm.

2. Diamond Path

Diamond Graph

This diamond shaped rail network tests if the merging paths works as expected.

3. Multi Path

Multi Graph

Same as before, just with multiple possible paths.

4. Loop

Loop Graph

In this railroad there are two possible loops, 1-2-1 and 1-3-2-1, this ensure that the algorithm correctly computes the fixpoint.

5. Complex rail

Complex Graph

This "complex" situation is obtained by adding to the previous loop configuration a double ending for the trains, through those two "parallel" tracks from Station5 to Station6 and from Station4 to Station7. Also a self loop on Station5 is introduced.