A fast Queue for Routing in PHP

Lets honour the title of this blog, and talk about routing.

Routing is the process of selecting paths in a network.

(from Wikipedia).

At RouteYou we are interested in all sorts of paths in street networks :

• Shortest walk route
• Shortest cycling route
• Nicest walk route
• Nicest cycling route
• …

In the past we used the breadth-first search algorithm to calculate those paths. Recently we changed to A* as Graph search algorithm, but that’s a story for later.

Let me explain step-by-step how the shortest path between 2 nodes is found using the breadth-first search algorithm :

1. Enqueue the start node.
2. Dequeue a node and examine it. If it is the destination node, the result has been found. Else enqueue all unknown nodes that can be accessed through the node examened.
3. If the queue is empty, quit the search without a result.
4. Repeat from step 2

An important part in the algorithm is the queue. Our first implementation of a queue looked like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Queue
{
    private $_queue = array();
 
    public function enqueue($item)
    {
        $this->_queue[] = $item;
    }
 
    public function dequeue()
    {
        return array_shift($this->_queue);
    }
}

Filling it with 10000 items takes about 0.075 seconds. Getting those 10000 items back out takes about 1 second.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Queue
{
    private $_queue = array();
    private $_pointer = 0;
 
    public function enqueue($item)
    {
        $this->_queue[] = $item;
    }
 
    public function dequeue()
    {
        return $this->_queue[$this->_pointer++];
    }
}

The code to enqueue items hasn’t changed. Getting 10000 items out of this improved queue takes only about 0.12 seconds, which is almost 10 times faster.