Letournel\PathFinder\Algorithms\ShortestPath\Dijkstra

Complexity

Total Complexity

10

Size/Duplication

Total Lines	67
Duplicated Lines	0 %

Coupling/Cohesion

Components	1
Dependencies	6

Importance

Changes

0

4 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	0	4	1
A	setGrid()	0	4	1
A	computeLength()	0	6	1
C	computePath()	0	38	7

<?php

namespace Letournel\PathFinder\Algorithms\ShortestPath;

use Letournel\PathFinder\AlgorithmShortestPath;
use Letournel\PathFinder\Core\Node;
use Letournel\PathFinder\Core\NodeGrid;
use Letournel\PathFinder\Core\NodeMap;
use Letournel\PathFinder\Core\NodePath;
use Letournel\PathFinder\Core\NodePriorityQueueMin;
use Letournel\PathFinder\Distance;

class Dijkstra implements AlgorithmShortestPath
{
    /*
     * For more info see
     * http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
     */
    
    private
        $distance,

It is generally advisable to only define one property per statement.

The visibility should be declared for property $distance.

        $grid;
    
    public function __construct(Distance $distance)
    {
        $this->distance = $distance;
    }
    
    public function setGrid(NodeGrid $grid)
    {
        $this->grid = $grid;
    }
    
    public function computeLength(Node $source, Node $target)
    {
        $shortestPath = $this->computePath($source, $target);
        
        return $shortestPath->computeLength($this->distance);
    }
    
    public function computePath(Node $source, Node $target)
    {
        if(! $this->grid instanceof NodeGrid)
        {
            throw new \RuntimeException('Invalid Grid');
        }
        
        $priorityQueue = new NodePriorityQueueMin();
        $distanceMap = new NodeMap();
        $previousMap = new NodeMap();
        
        $priorityQueue->insert($source, 0);
        $distanceMap->insert($source, 0);

0 is of type integer, but the function expects a boolean.

        
        while(! $priorityQueue->isEmpty())
        {
            $node = $priorityQueue->extract();
            
            if($node->getId() === $target->getId())
            {
                return new NodePath($previousMap->lookupFrom($node));
            }
            
            $neighbors = $this->grid->getWalkableNeighbors($node);
            foreach($neighbors as $neighbor)
            {
                $alternativeDistance = $distanceMap->lookup($node) + $this->distance->compute($node, $neighbor);
                if(! $distanceMap->exists($neighbor) || $alternativeDistance < $distanceMap->lookup($neighbor))
                {
                    $priorityQueue->insert($neighbor, $alternativeDistance);
                    $distanceMap->insert($neighbor, $alternativeDistance);
                    $previousMap->insert($neighbor, $node);
                }
            }
        }
        
        return array(); // no path found
    }
}