Hi there,
I’m trying to add an offline navigation/pathfinder element into the app I’m building. Some apps already have similar capability but ofc I can’t quite nick their datasets, and considering there are 375ish stations more or less, building a 375^2 grid would be ~140k API calls (as a one-off, but still.), plus a fair bit of data stored. Essentially I think I need to build a grid of what distance (travel time) is each station from one another.
Any suggestions on how I could this efficiently and without pissing all the DBAs off? 
– I could automate the API calls to 1/sec or 1/every 2 sec and leave the computer on but I still think doing that many calls is an overkill.
Thanks
Don’t think I’m qualified enough to suggest how to do this with the API, especially efficiently and without making too many calls, but if you’re willing to put in a bit of effort you should take a look at the TfL Working Train Timetables.
While working on a project at school I used the WTTs to get the average travelling time between stations in both directions. I chose to store the data as a graph rather than a matrix/grid, as that would get pretty big with a lot of empty values where stations don’t connect.
To find the quickest route between stations you could use Dijkstra’s algorithm to find the shortest path, using the travel time as the weight.
Have you considered using Dijkstra? You can model a transport network in a couple of hundred lines of code? Dijkstra's algorithm - Wikipedia
I find it a very fast and efficient way to model the TfL network. You can pop in all the necessary nodes (tube, dlr, tram,Overground and interchanges/junctions) and end up with a tiny dataset of pointers which you can easily use offline.
You can also use it to find the quickest route between two points by a simple traversal of the list of pointers.
class NewDijkstra
{
/*
* This version of Dijkstra:
*
* - use PHP arrays to store the nodes and their pointers
*
*
*/
/*
* E. W. Dijkstra. "A Note on Two Problems in Connexion with Graphs". Num. Math. 1 (1959), 269-271.
* V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Chapter 10, Cambridge University Press (2017)
* V. Latora, V. Nicosia, G. Russo, "Complex Networks: Principles, Methods and Applications", Appendix 6, Cambridge University Press (2017)
*/
public $dist = [];
public $prev = [];
public $arrMyNodes = [];
public $arrMyLinks = [];
public $arrMyIDs = [];
public $strEcho = __CLASS__;
public $arrReturn = [];
public $strTiming = "";
public $arrLatLong = [];
public $fpStartTime;
public final function addNode($strID, $arrStuff = [])
{
$this->arrMyNodes[] = $arrStuff;
end($this->arrMyNodes);
$strKey = key($this->arrMyNodes);
$this->arrMyIDs[$strID] = $strKey;
return $strKey;
}
public final function addLink($strID1, $strID2, $fpWeight1 = 1, $fpWeight2 = null)
{
if ($fpWeight2 === null) {
}
$fpID1 = $this->arrMyIDs[$strID1];
$fpID2 = $this->arrMyIDs[$strID2];
$this->arrMyLinks[$fpID1][$fpID2] = $fpWeight1;
}
public function lookupLocation($strCode)
{
if (substr($strCode, 0, 1) === "_") {
return $this->arrLatLong[$strCode];
} else {
if (isset($this->arrLatLong[substr($strCode, 0, 3)])) {
return $this->arrLatLong[substr($strCode, 0, 3)];
}
return ["n" => 51, "e" => 0];
}
}
public final function readShortestTo($strID2)
{
$fpID2 = $this->arrMyIDs[$strID2];
$this->strEcho .= PHP_EOL . "Starting from node " . $fpID2 . " " . $this->dist[$fpID2] . "km...";
do {
$this->arrReturn[] = ["id" => $this->getCodeFromNodeID($fpID2), "display" => $this->arrMyNodes[$fpID2]];
$fpID2 = $this->prev[$fpID2];
} while ($fpID2 > -1);
$this->strEcho .= PHP_EOL . PHP_EOL;
}
public final function getCodeFromNodeID($fpID2)
{
return array_search($fpID2, $this->arrMyIDs);
}
public function getShortestFrom($strID1)
{
$fpID1 = $this->arrMyIDs[$strID1];
$this->getShortestFromOriginal($fpID1);
}
public function getShortestFromOriginal($fpID1, $fpID2 = INF)
{
/*
*
* Implementation of the Dijkstra algorithm
*
* The algorithm is illustrated in Dijkstra.PNG
*
*/
$this->cleanUp();
/*
* At each iteration, each node of the graph is in one of three possible states: current, visited or unvisted.
*
*
*/
/* The algorithm makes used of the array $dist[] to store the tentative distances from each nodfe from node i,
* wilst the array $prev[] contains the label of the tentative predecessor of each node.
*
*/
$dist = [];
$prev = [];
$visited = [];
/*
* Initially, all the nodes are marked as unvisited and are included in the set U of unvisited notdes.
* Each node j!==i is assigned a tentative distance d(i,j) = INF from node i, where the distance from node i
* to itself is set to zero...
*/
foreach ($this->arrMyNodes as $j => $arrTemp) {
$dist[$j] = INF;
$prev[$j] = -1;
$visited[$j] = INF;
}
$dist[$fpID1] = 0;
$visited[$fpID1] = 0;
do {
/* At each step, we choose the node in U with the minimal distance from i. We remove this node from U,
* and mark it was current.
*
* The nbode marked current at the first step is node i, since this is the only node having a finite tentative
* distance $dist[$i]=0.
*
* Then for each neighbour j of the current node, we consider the shortest path from i to j which includes
* the current node. We set $t_dist equal to the tentative distance of the current node from i plus the
* weight of the link connecting the current node to j.
*
* If $t_dist is smnaller than dist[j], then t_dist becomes the new tentative distance from i to j, and the
* current node is set as the predecessor of j.
*
*/
$cur_node = self::returnMinKey($visited);
if ($cur_node < INF) {
/*
* When computing the node values for $t_dist, only use nodes that are unvisited!
*
*/
foreach ($this->arrMyLinks[$cur_node] as $j => $fpWeight) {
if (isset($visited[$j])) {
$t_dist = $dist[$cur_node] + $fpWeight;
if ($t_dist < $dist[$j]) {
$dist[$j] = $t_dist;
$visited[$j] = $t_dist;
$prev[$j] = $cur_node;
}
}
}
/*
* When all of its neighbours have been processed, the current node is marked as visited. Once a node is
* marked
* as visited, its distance from node i is final and mininal, and thge node is not considered anymore.
*
* The algorithm stops when the set U is empty, or when the current ndoe has infinite distance from i. In
* the latter case, all of the other nodes contained in U do not belong to the same component of i, and are
* therefore unrachable.
*/
unset ($visited[$cur_node]);
}
if ($cur_node === $fpID2) {
$cur_node = INF;
}
} while ($cur_node < INF);
$this->prev = $prev;
$this->dist = $dist;
}
public final function cleanUp()
{
/*
* Remove nodes that have no connections to other nodes
*
*/
foreach ($this->arrMyNodes as $strID => $arrRow) {
if (!isset($this->arrMyLinks[$strID])) {
unset($this->arrMyNodes[$strID]);
unset($this->arrMyIDs[array_search($strID, $this->arrMyIDs)]);
}
}
}
public static function returnMinKey(&$dist)
{
if (count($dist) > 0) {
return array_search(min($dist), $dist, true);
} else {
return INF;
}
}
public function getShortestFromAndTo($strID1, $strID2)
{
$this->setTimingStart();
$fpID1 = $this->arrMyIDs[$strID1];
$fpID2 = $this->arrMyIDs[$strID2];
$this->getShortestFromOriginal($fpID1, $fpID2);
$this->recordATiming();
}
public function setTimingStart()
{
$this->fpStartTime = microtime(true);
}
public function recordATiming()
{
$this->strTiming .= cronLogger::timeAgo($this->fpStartTime) . " ";
}
}
Thanks both, will have a look at that algorithm as well as the working time tables!
thanks again
2 Likes
Hello, I’m a little late, but I’ve been needing a very similar thing and been stuck trying to find a solution for a long time. If you’re still stuck, I’ve found a solution thats not perfect but should be more than good enough for what I need so hopefully would be for you too.
There’s a rough datasource here: GitHub - nicola/tubemaps: Browser, NodeJs library and command-line tool for handling tube data, its a little old but can be cleaned up relatively easily.
I’ve been using neo4j to store the dataset and query it for travel times. If you want it available offline you could use neo4j and the graph data science plugin and store the results of the All Pairs Shortest Path procedure to query more easily.