Letournel\PathFinder\Algorithms\ShortestDistance\Dijkstra

Complexity

Total Complexity

12

Size/Duplication

Total Lines	69
Duplicated Lines	27.54 %

Coupling/Cohesion

Components	1
Dependencies	4

Importance

Changes

0

4 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	0	4	1
A	setGrid()	0	6	1
A	computeLength()	19	19	4
B	computeDistanceGraph()	0	24	6

<?php

namespace Letournel\PathFinder\Algorithms\ShortestDistance;

use Letournel\PathFinder\AlgorithmShortestDistance;
use Letournel\PathFinder\Core\Node;
use Letournel\PathFinder\Core\NodeGraph;
use Letournel\PathFinder\Core\NodeGrid;
use Letournel\PathFinder\Core\NodePriorityQueueMin;
use Letournel\PathFinder\Distance;

class Dijkstra implements AlgorithmShortestDistance
{
    /*
     * 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.

        $distanceGraph,
        $grid;
    
    public function __construct(Distance $distance)
    {
        $this->distance = $distance;
    }
    
    public function setGrid(NodeGrid $grid)
    {
        $this->grid = $grid;
        $this->distanceGraph = new NodeGraph($grid->buildWalkableNodesList());
        $this->distanceGraph->setSymetricMode(false);
    }
    
    public function computeLength(Node $source, Node $target)

This method seems to be duplicated in your project.

    {
        if(! $this->grid instanceof NodeGrid)
        {
            throw new \RuntimeException('Invalid Grid');
        }
        if(! $this->distanceGraph instanceof NodeGraph)
        {
            throw new \RuntimeException('Invalid Graph');
        }
        
        $edges = $this->distanceGraph->getEdgesFrom($source);
        if(empty($edges))
        {
            $this->computeDistanceGraph(array($source));
        }
        
        return $this->distanceGraph->getEdgeBetween($source, $target);
    }
    
    private function computeDistanceGraph(array $nodesList)
    {
        foreach($nodesList as $source)
        {
            $priorityQueue = new NodePriorityQueueMin();
            $priorityQueue->insert($source, 0);
            
            while(! $priorityQueue->isEmpty())
            {
                $node = $priorityQueue->extract();
                
                $neighbors = $this->grid->getWalkableNeighbors($node);
                foreach($neighbors as $neighbor)
                {
                    $alternativeDistance = $this->distanceGraph->getEdgeBetween($source, $node) + $this->distance->compute($node, $neighbor);
                    if(! $this->distanceGraph->existsEdgeBetween($source, $neighbor) || $alternativeDistance < $this->distanceGraph->getEdgeBetween($source, $neighbor))
                    {
                        $priorityQueue->insert($neighbor, $alternativeDistance);
                        $this->distanceGraph->createEdgeBetween($source, $neighbor, $alternativeDistance);
                    }
                }
            }
        }
    }
}