Path-Finding in Subway Networks

[Ángel Martin]

I've been working on another MCODE project for the last few weeks that it's getting close to completion. It's quite ambitious in that it was totally new for me, so I've had to do some initial research to see how to approach it. The project in question is to find connecting paths in a subway network (or any other kind) so the user can go from station A to station B, regardless of the number of transfers required. That really piqued my curiosity to the point of attempting some leverage with the Dictionary/Country ROMS core routines for table searches, but the core stuff (i.e. the path-finding itself) was a big dark area and I had to develop new tricks to tackle it...

I won't pretend that my implementation is of any ground-breaking importance but I sure am having a ball tangled-up with these pesky concepts, keeps my aging mind (relatively) fit. Certainly much of the literature I checked (Traveling Salesman, Djikstra's algorithm, et al) doesn't lend itself to easy versioning as MCODE).

The first example is the Madrid Metro (all those rides of my youth had to be honored ;-) It's an 8k Module, as the "MAP" part already takes over 3,200 bytes - holding the station names and line topology "coordinates". I've already solved the 1x and 2x- transfer scenarios which cover about 90% of the cases, but the remaining 10% are a tough nut to crack... will let you know when it's ready to see the limelight, although this is a very idiosyncratic module so not likely to create much interest (as if I cared, right?).

Does this strike a chord with anybody out there?

To be continued...

[Paul Dale]

I played around with this kind of thing building word graphs (change one letter to make the next word in the sequence, optionally rearranging the letters). My first thought is to use Djikstra's original algorithm which avoids the priority queue but runs in O(n²) time. I'd make links along a line cost 1 and a transfer cost 10⁶ or similar -- this favours staying on a train over more transfers. The result will indicate the number of stations and the number of transfers and the path can be backtracked from the final station.

To downplay transfers, make everything cost one. In this case, the algorithm can be stopped once the destination is reached since no path can be shorter.

I went on to search for maximal diameters in the graphs.


Pauli

[Ángel Martin]

Pay heed folks, the MetroPaths module is ready and has been submitted to the usual channels (CL Library, et al). Judging from the overwhelming responses to this thread I'm not going to bother to post it here as attachment, but you're really missing out something special ;-)

Supports up to three-transfer connections (four lines), with branch optimization for 1-transfer situation - choosing the shorter sub-path (with fewer number of stops) when local loops exist. This is used as recurrent module for the 2- and 3-transfer cases.

Comes with the Madrid Map in the upper page so you can put it to work immediately.

Here's where you can download the manual if interested - thanks to Monte:
http://systemyde.com/pdf/Path-Finding_in...tworks.pdf

Happy metro riding!
ÁM.

[pier4r]

Nice work, I do assume that those threads requires a bit of effort, for this they receive little activity (see bike shedding). I myself I skimmed your pdf. Surely I wish all the user created libraries would be as documented as yours.

@Paul Dale: any chance that you have a repository of your trials?

[Giancarlo]

Hello,
This subject has been in my head for long time now and i didn't know where to start.

I hope i can free my mind soon to focus on this (using a different machine) and the subway network of Milan (simplier).

Thanks for the docs you prepared and the algorithm reference. I'am going to try to understand them.

I remember some programs for hp48, very simple to understand how to go from A to B or Ato C in a kind of grid resembling your network.

Thanks for your work,

Giancarlo

[Ángel Martin]

A second map is now available: The London Tube.

Glad to say the model holds tight and the algorithms work as expected on both maps. A few constants in the original revision have now been changed into variables, with the actual values read from the map pages.

Cheers,
ÁM