Spider Metro

I got this one almost ready.

It was going to be part of my final project in computational physics, but I decided to leave it aside. My reasons: Well, in a trip to the mountains near Madrid, while chatting to our driver - a professional programmer  for an IT company - she mentioned her master thesis project...and then it hit me. She had solve the problem of  the spider metro. Not only that, she had designed a much more efficient and robust solution than mine...too bad.

I have not described the spider metro problem yet, so let me start by doing so.

The original problem I got in mind was to find the shortest way to get from point A to point B in a city using the metro, kind of what Google maps offers, except that it would be self contained, at least in it's simplest versions.

The idea of the solution was similar to something I saw on Prison Break, the tv series: They wanted to know weather a water pipe led to a specific opening, so they put a little origami bird in point A, let it go with the flow, and finally check if the origami bird was indeed at point B. Well, my solution is similar, but with many origami birds:

You would start by putting an origami bird at the closest metro station to point A in the city. Now, in the simplest case, only one metro line goes through that station. In this case, our origami bird will replicate itself (so we will have two birds); One bird will go one way and the other bird will go the other way. In the simplest version of the solution, which I called: "without a compass" we don't have any preference for one of the two directions. However, this preference can be implemented later by including a "compass", or a way to discern weather one direction will take you away instead of taking you towards your desired point.

What happens when the birds arrive to a new station? Given that they arrive to a station where n-metro lines converge, the birds will replicate (2n-2) times. now we have 2n-2+1 birds (counting the original bird). How many paths can be followed? well, each metro line can be followed in two different directions, and since we are not trying to come back to the same line we came through, then we are talking about 2n-1. Incidentally, the same number of birds that we now have.

Next step is, as you would expect, to send each bird down a line and repeating the process each time they get to a new station. This algorithm implies that if a bird reaches the end of a line, it will simply "disappear". It will not go back or anything like that.

Eventually, one bird will reach the station closest to point B (indicated as an input of the problem), then we will see where it came from, which turns it took, and so on, and we will have our solution to the shortest path.

Now, how sure are we about the "shortness" of this solution? is it really the shortest? Well, I think that if we follow the algorithm down to every detail, i.e. If we indeed replicate 2n-2 times, and cover all the possible lines at every node (station), then the solution we obtain WILL be the best one. If we leaf some line un-attended, we can't warranty the solution you will obtain will be the best.

Moreover, remember that when the bird arrives to a new station it will not go back the same path it came from? well, if you allow it to go back, you will have several birds arriving to point B ! The best solution in this case will be, as you would expect, the one given by the first bird, the fastest bird. Is important to notice that if the "going-back" option is turned off, only one bird, the best bird, will arrive to point B. 

Now, you can improve this model in a very nice way. So far we have been working over the metro plan, which for us is a series of nodes located at different coordinates over the surface of the earth, and joined by "straight" paths (to first approximation). Well we could for instance include trains with different velocities. Some metro lines have faster/newer train and thus they travel faster. We could also take into account the discreteness of the time schedules!. Trains will only come at specific times (until now we were assuming the trains were ready for us, waiting for our birds to arrive) but this is not the case in real life. We can also superpose several node-maps. One for regular trains, and one for express trains, trains that don't stop in every station, but only at some of them. Finally we can include node-maps for the regional trains (at least the stations that lie within the city), and buses, and trams.

A final touch will include the node-map of the streets of the city. Each corner will be a map, joined by straight lines (street) each line of this map is supposed ot be travel at walking speed and so on.

This was my project for computational physics, it seemed super fun at the time, but then I went into this trip, and this girl start talking about her Master thesis project, and guess what....it was the spider metro!, or course she didn't called like that, but it was the very same thing. 

I am an amateur programmer, so I though about making the simplest version of the spider metro in one long code. She however, said that the best way to do so was to divide the task in modules. Modules that will take care of specific features, like the replication of the bird at the nodes, or the traveling down the lines at the specific speed, another module for scheduling, and so on. These modules could then be tested separately, and modified independently in case the program needed to be changed. In general, these modules come with many advantages! Since then I do my best to divide my programs into modules, and work on them as independent programs. 

By the way, I called spider metro, because I imagine, that in the first stages there will be a dozen birds traveling away from the "center" like spider legs....thus the name.