Recursive routeing guide

[Bletchleyite]

Putting in a new speculative thread to delve into this more.

@Bletchleyite how would you intend to express the valid routes in a file? Would you apply a limit to the depth of recursion? Otherwise you would end up with cycles.

Station from
Station to
List of permitted via stations

That's the data you need. You basically stop when you get to a via station that doesn't offer a drill down, which would be a station pair where there is only one route on which a passenger service operates.

You would need something to stop it looping, e.g. if you had Stockport-Euston valid via Manchester and Manchester-Euston valid via Stockport. The logic for that isn't immediately straightforward, but it's a case of "don't explore a route that has already been explored".

 

[crablab]

@Bletchleyite how would you intend to express the valid routes in a file? Would you apply a limit to the depth of recursion? Otherwise you would end up with cycles.

eg. (KGX -> FPK -> ENC -> SVG -> FPK...)

A common approach would just be to calculate the shortest path applying an upper bound to the number of nodes you check, but that might be that you then never evaluate routes you do intend to be be valid.

It's also important to decide how you weight the paths between nodes. Distance? Time? (since the general shortest path would simply be the shortest path between nodes, which isn't necessarily practically correct)

And routes which require changes or cross-London would need to incur a penalty.

Very much a 1st year CS problem

 

[Bletchleyite]

You're overcomplicating it (as CS students usually do compared with real world business IT). No routes need to incur a penalty. All this is is a system to enumerate the full set of permitted routes, not to work out fares.

I'm not clear what would give you the above because there is no case for Kings Cross to Finsbury Park to be valid via Stevenage, unless your name is "Clive D.W. Feather" of uk.railway fame. KGX to FPK is an end node - a journey which can only be made by one route.

 

[crablab]

as CS students usually do compared with real world business IT

I regret I am no longer a student, although software engineers are wont to overengineer

It's partly just me thinking it through out loud.

I'm not clear what would give you the above because there is no case for Kings Cross to Finsbury Park to be valid via Stevenage,

This was a bad example because of where Finsbury Park is, but I think your DFS would still find a valid route to (say) Brookmans Park via Stevenage and the Hertford Loop, as well as via Finsbury Park. Would you want that to be valid? It technically is on map KP at the moment.

 

[miklcct]

I regret I am no longer a student, although software engineers are wont to overengineer

It's partly just me thinking it through out loud.

This was a bad example because of where Finsbury Park is, but I think your DFS would still find a valid route to (say) Brookmans Park via Stevenage and the Hertford Loop, as well as via Finsbury Park. Would you want that to be valid? It technically is on map KP at the moment.

For example, the route definition can be:

Kings Cross - Brookmans Park: via Finsbury Park
Kings Cross - Finsbury Park: direct
Finsbury Park - Brookmans Park: direct

Then Stevenage can't be used on the journey

 

[sheff1]

A recursive Routeing Guide would be more sensible in my view.

For example, in the current RG Derby to London is valid via Tamworth and the WCML. Sheffield to London is valid via Derby so should logically be then valid onwards via Tamworth but isn't. You then have the opposite where Derby to York is valid via Barnsley, but Sheffield to York is not.

 

[Kilopylae]

This was a bad example because of where Finsbury Park is, but I think your DFS would still find a valid route to (say) Brookmans Park via Stevenage and the Hertford Loop, as well as via Finsbury Park. Would you want that to be valid? It technically is on map KP at the moment.

Couldn't one simply set up the system to flag up any routes between station pairs which seem suspiciously long (e.g. are more than twice the crow's-eye distance) and then allow a human to approve them manually or prohibit them with negative easements?

There can't be that many station pairs with circuitous direct services between them that avoid all invalid via points.

 

[greatkingrat]

The way I would do it is for each journey, just list the first routeing point encountered on each permitted route. Then when you get to the first routeing point, you look up the journey from there to the destination, and so on. Subject to the rule that you can't pass through any routeing point twice to prevent overly circuitous routes.

Journey from A to Z: Valid via B or C
if you choose to go via B then you look up B to Z
Journey from B to Z: valid via D or E
Journey from D to Z: only valid direct
so A-B-D-Z is a permitted route

Although it may be time consuming to find all permitted routes manually with this method, it would be trivial for a computer to work through all the various branches and list all permitted routes.

 

[Western 52]

Years ago I wrote a program in PROLOG which did this sort of recursive analysis using the railway network in the west of England as an example. No idea if that language still exists, but it was easy to set up routing rules to avoid lengthy or circuitous routes.

 

[crablab]

Years ago I wrote a program in PROLOG which did this sort of recursive analysis using the railway network in the west of England as an example. No idea if that language still exists,

Unfortunately for me, it very much does. PROLOG is a language that works very differently to my brain - it wasn't a fun course. I still managed to pass!