MySQL query to get a travel route

Question

I have the following table:

+--------+----------+---------+---------+---------
|  From  |    To    |Departure| Arrival |   ID   | 
+--------+----------+---------+---------+---------
|   A    |    B     |   0900  |   0930  |   1    | 
+--------+----------+---------+---------+---------
|   C    |    D     |   1000  |   1030  |   2    | 
+--------+----------+---------+---------+---------
|   B    |    C     |   1100  |   1130  |   3    | 
+--------+----------+---------+---------+---------
|   D    |    E     |   1200  |   1230  |   4    | 
+--------+----------+---------+---------+---------
|   C    |    D     |   1300  |   1330  |   5    | 
+--------+----------+---------+---------+---------

• Departure/Arrival time and ID are always ascending;
  
• C_D can be found before and after B_C.
  
  

I wish to go from A to D, so the travel route should be ID1, ID3, ID5 or A_B, B_C, C_D.

Any help is appreciated.
Thanks.

Answer 1

You could solve this in a stored procedure. But this algorithm will probably be faster when executed in memory by a programming language. Just make sure that you have the complete data set loaded, so you won't have to execute a query every iteration.

pseudo code:

to = 'D'
prev_to = 'A'
array = array();
while (prev_to != 'D') {
  select arrival, to into prev_arrival, prev_to
  from table 
  where departure > prev_arrival 
  and from = prev_to;

  array[] = [arrival => prev_arrival, to => prev_to]
}

return array

Edit: I guess I had nothing better to do ;)

This class will search all routes from A to D between given start and end time. Just like a public transport app. You might want to use your own database connection methods. (Just don't use mysql_* functions anymore)

<?php

class RoutePlanner
{
    /** @var string */
    protected $departureTime;
    /** @var string */
    protected $departureLocation;
    /** @var string */
    protected $arrivalTime;
    /** @var string */
    protected $arrivalLocation;
    /** @var array */
    protected $schedule;
    /** @var mysqli */
    protected $db;

    /**
     * @param string $departureTime
     * @param string $departureLocation
     * @param string $arrivalTime
     * @param string $arrivalLocation
     * @throws InvalidArgumentException
     */
    public function __construct($departureTime, $departureLocation, $arrivalTime, $arrivalLocation)
    {
        $this->departureTime = $departureTime;
        $this->departureLocation = $departureLocation;
        $this->arrivalTime = $arrivalTime;
        $this->arrivalLocation = $arrivalLocation;
    }

    /**
     * @return array
     */
    public function getRoutes()
    {
        $schedule = $this->fetchSchedule();
        $routes = $this->searchRoutes($schedule);
        return $routes;
    }

    /**
     * Search all routes that start and end between given times
     * @param array $schedule - passing as parameter to ensure the order of execution
     * @return array
     */
    protected function searchRoutes(array $schedule)
    {
        $routes = array();

        foreach ($schedule as $i => $row)
        {
            if ($row['from'] == $this->departureLocation)
            {
                $routes[] = $this->getRoute($schedule, $i);
            }
        }

        return $routes;
    }

    /**
     * Get the route when starting at given point and time
     * @param $schedule
     * @param $start
     * @return array
     */
    protected function getRoute($schedule, $start)
    {
        $steps = array();

        $from = $this->departureLocation;
        $time = $this->departureTime;

        for ($i = $start; $i < count($schedule); $i++)
        {
            $row = $schedule[$i];
            if ($row['from'] == $from && $row['departure'] > $time)
            {
                $steps[] = $row;
                $from = $row['to'];
                $time = $row['arrival'];
            }
        }

        return $steps;
    }

    /**
     * @return array
     */
    protected function fetchSchedule()
    {
        if (! empty($this->schedule))
            return $this->schedule;

        $sql = "select * from schedule where departure >= ? and arrival <= ?";

        $db = $this->getDatabase();
        $statement = $db->prepare($sql);
        $statement->bind_param("ss", $this->departureTime, $this->arrivalTime);
        $statement->execute();
        $result = $statement->get_result();

        $this->schedule = $result->fetch_all(MYSQLI_ASSOC);

        $statement->close();
        $result->free();

        return $this->schedule;
    }

    /**
     * @return mysqli
     */
    protected function getDatabase()
    {
        if (empty($this->db))
            $this->db = new mysqli('localhost', 'user', 'pass', 'database');

        return $this->db;
    }

    public function __destroy()
    {
        if (! empty($this->db))
            $this->db->close();
    }
}

Use like:

<?php

$planner = new RoutePlanner('Amsterdam', '0300', 'Berlin', '1030');
$routes = $planner->getRoutes();