Here's my idea. It involves looking at the data from a different angle.
Instead of arrays of stop numbers
$routes[0] = array(1,2,3,4,5);
$routes[1] = array(1,2,3,13);
...
or (because those probably aren't the real route numbers)
$routes['250'] = array(1,2,3,4,5);
$routes['321] = array(1,2,3,13);
...
I'm going to have a single array with all of the individual legs (each leg is a pair of stops), keeping the information about which routes they belong to so that such information can be recovered later. I found it easier to think of a route as a series of trips between stops rather than just a series of stops.
$legs = array(
array(1,2,'250'),
array(2,3,'250'),
array(3,4,'250'),
array(4,5,'250'),
array(1,2,'321'),
array(2,3,'321'),
array(3,13,'321'),
...
);
A conversion function to do this:
function routes_to_legs($routes)
{
$legs = array();
foreach($routes as $routeno>=$route)
{
for($i=0; $i<count($route)-1; $i++)
{
$legs[] = array($route[$i], $route[$i+1], $routeno);
}
}
return $legs;
}
Now we can build up every possible route leg by leg.
A route will be an array of legs (legs, instead of stop numbers, because route numbers change at some stops). This function will take an existing route, and find all the ways to extend it by one leg:
function extend_route($legs, $route)
{
$last_stop = $route[count($route)-1][1];
$extended_routes = array();
foreach($legs as $leg)
{
if($leg[0]==$last_stop) // a leg taht starts where this route ends
{
if(in_array($leg[1], $route)) continue; // but it would form a loop
$extended_route = $route;
$extended_route[] = $leg;
$extended_routes[] = $extended_route;
}
}
return $extended_routes;
}
We start with an array of the one-leg routes that start from our starting stop (so to speak).
function legs_starting_from($legs, $start)
{
$routes = array();
foreach($legs as $leg)
if($leg[0]==$start)
$routes[] = $leg;
return $routes;
}
Now that we've got those, we can extend them until they all stop at our stopping stop.
$itineraries = legs_starting_from($legs, $start);
$complete_journeys = array(); // We'll remove complete journeys from $itineraries and put them here
while(count($itineraries))
{
$itinerary = array_shift($itineraries); // Shortens $itineraries by one
$extended_itineraries = extend_route($legs, $itinerary);
foreach($extended_itineraries as $itinerary)
{
if($itinerary[count($itinerary)-1][1]==$stop)
$complete_journeys[] = $itinerary;
else
$itineraries[] = $itinerary;
}
}
The result will be (should be - it's not like I've run this code or anything) an array of possible routes; each route being from $start to $stop, and consisting of an array of legs (like $legs, showing where each $leg starts, where it ends, and which route it's part of).
