diegomtassis / train-routing-problem Goto Github PK

Diego Martín Tassis - August 2015

Sample application built in order to practice a little bit of TDD.

It might be seen as a Code Kata.

The idea was to use as less 3rd party libraries as possible.

The problem is a simplification of the Vehicle routing problem.

Given a train network described using a graph where the arcs are tracks and vertices are cities:

• The cities are represented by letters [A-Z].
• The tracks are labeled with a distance.
• A track between A and B doesn't imply the existence of a track between B and A.
• If 2 tracks AB and BA exist, they do not need to have the same distance.
• There are cities which are not connected.
• There is not more than 1 track connecting 2 cities.

Build services in order to:

• Given a route, e.g. ABCDE, check whether it exists in the network and return its distance.
• Calculate all the routes connecting 2 cities (may be the same city) separated by a number of stops between n and m.
• Calculate all the routes connecting 2 cities by a distance lower than n.
• Calculate the shortest route connecting 2 cities. When more than one, return all.

Given the following train network: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7, FH10, FG3, GH4, XZ50, XY30, YZ20

Provide the right output for the following scenarios:

Expected output: 9

Expected output: 5

Expected output: 13

Expected output: 22

Expected output: NO SUCH ROUTE

Expected output: CDC (2 stops), CEBC (3 stops)

Expected output: ABCDC, ADCDC, ADEBC

Expected output: 9

Expected output: 9

Expected output: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC

• maven 3
• java 8

Go to the root folder and execute:

mvn clean install

There are some java static invokers created just for demonstration/test purposes.

These invokers are pretty simple and include no validation at all (validation is performed starting at the application layer), so if an integer argument is expected and an invalid value is provided the result will be the exception generated by the invoker, since the real application layer is not even invoked.

This is not the only disadvantage of the invokers. The application is developed in such a fashion that would be rather easy to create a microservice (out of the scope of this exercise, the most simple way would be to use Spring Boot) and expose it via rest. This would allow to take advantage of the fact that the services learn/cache information which make following executions to perform better, which of course doesn't happen when the invokers are invoked isolated.

Another possibility for execution is to create an integration test similar to the ones under /client/src/test/java, load the application services from the DI context and execute.

The evidence that the application works with the test samples provided within the description is accomplished by executing

com.dmt.train.routing.client.RequiredSampleITest

which is located in the client module.

Move to the /client/target folder and execute:

(If needed, the sample input file under /client/test/resources may be used).

• java -cp client-0.0.1-SNAPSHOT-shaded.jar com.dmt.train.routing.client.DistanceCalculator

• java -cp client-0.0.1-SNAPSHOT-shaded.jar com.dmt.train.routing.client.TripsFinderByStops

• java -cp client-0.0.1-SNAPSHOT-shaded.jar com.dmt.train.routing.client.TripsFinderByDistance

• java -cp client-0.0.1-SNAPSHOT-shaded.jar com.dmt.train.routing.client.TripsFinderWithMinimumDistance

Standard maven multi module layout.

• root: aggregator and parent pom for the submodules.
• application-api: abstractions for the application layer
• domain-api: abstractions for the domain layer
• service: service implementations
• client: invokers for the application services and integration tests
• utils: general purpose utilities (derived from the commandment of not using 3rd party libraries)

Each module respects the maven standard layout for code, tests and resources.

DDD approach. Architecture and application roles as suggested by Eric Evans in his book "Domain Driven Design".

Not only at the class/component but also at the bundle level (modularization).

• Recoverage after validation failures not implemented, so only unchecked exceptions are thrown.

• Spring fwk context library used as dependency injection framework (only in the client module).
• JSR-330 annotations in the service module.
• At some point in time it was needed to choose between an iterative or recursive approach. Chose the iterative approach because a smaller memory footprint, though this is not very important when dealing with a low number of cities (e.g. the test sample).
• No specific algorithm optimization performed, apart from the usage of a repository for the graph and the already visited routes. Usually this kind of problems with graphs may be optimized by using a caching aspect to avoid solving the same problem more than once. This is easier when a recursive approach is used.

• Formatting done following the AAA pattern, but using the notation suggested by Martin Fowler in his article "Mocks aren't stubs".
• Naming of the tests following the suggestions done by Roy Osherove in his book "The art of Unit testing", except for the most-optimistic vanilla cases where I simply use the name of the method under test.
• EasyMock used as mocking framework
• TDD put in practice following a london/mockist approach as explained by Martin Freeman and Nat Pryce in the book "Growing Object-Oriented Software, guided by tests". This is:

1. Begin with a failing integration test describing an intermediate or final feature.
2. Identify responsibilities and create interfaces.
3. Implement interfaces and add unit tests for the implemented code (TFD).
4. The initial test gets green.
5. Refactor.

The integration tests created as driver for the TDD process are located inside the client module.

• Register a 2 point route. Done
• Register a 3 point route: invalid operation. Done
• Import a graph from a file. Done

• Get the distance of a 2 point existing route. Done
• Get the distance of a 2 point not existing route: null distance. Done
• Get the distance of a empty route: expected illegal argument. Done
• Get the distance of a route with invalid characters: expected illegal argument. Done
• Get the distance of a 5 edge route. Done
• Get the distance of a 5 edge non existing route: null distance. Done

• Get the trips between 2 points separated exactly by one stop, and the route exists. Done
• Get the trips between 2 points separated exactly by one stop, and the route does not exist. Done
• Get the trips between A and C separated exactly by 4 stops. Done

• Get the trips between C and C separated exactly by a distance lower than 30. Done
• Get the trips between C and C separated exactly by a distance lower than 5. Does not exist. Done

• Get the shortest trip between 2 cities when there is a direct route between then and it is the shortest route. Done
• Get the shortest trip between 2 cities when there is a multi-stop route shorter than a direct route between them. Done
• Get the shortest trip between 2 cities when there is not a route between them. Done
• Get the shortest trip between 2 cities when there is 2 routes with the same distance. Done