Mado\QueryBundle\Component\Meta\Dijkstra

Complexity

Total Complexity

18

Size/Duplication

Total Lines	78
Duplicated Lines	0 %

Importance

Changes

0

4 Methods

Rating	Name	Duplication	Size	Complexity
A	__construct()	0	5	3
A	shortestPaths()	0	18	4
B	processQueue()	0	20	7
A	extractPaths()	0	17	4

<?php

namespace Mado\QueryBundle\Component\Meta;

/**
 * @since Class available since Release 2.1.0
 */
class Dijkstra
{
    private $map;

    private $distance;

    private $prev;

    private $visited;

    public function __construct($map)
    {
        foreach ($map as $nodeName => $metaData) {
            foreach ($metaData['relations'] as $itemKey => $itemValue) {
                $this->map[$nodeName][$itemValue] = 1;
            }
        }
    }

    private function processQueue(array $excluded)
    {
        $node = array_search(min($this->visited), $this->visited);

        if (!empty($this->map[$node]) && !in_array($node, $excluded)) {
            foreach ($this->map[$node] as $neighbor => $cost) {
                if (isset($this->distance[$neighbor])) {
                    if ($this->distance[$node] + $cost < $this->distance[$neighbor]) {
                        $this->distance[$neighbor] = $this->distance[$node] + $cost;
                        $this->prev[$neighbor] = [$node];
                        $this->visited[$neighbor] = $this->distance[$neighbor];
                    } elseif ($this->distance[$node] + $cost === $this->distance[$neighbor]) {
                        $this->prev[$neighbor][] = $node;
                        $this->visited[$neighbor] = $this->distance[$neighbor];
                    }
                }
            }
        }

        unset($this->visited[$node]);
    }

    private function extractPaths($target)
    {
        $paths = [[$target]];
        while (current($paths) !== false) {
            $key  = key($paths);
            $path = current($paths);
            next($paths);
            if (!empty($this->prev[$path[0]])) {
                foreach ($this->prev[$path[0]] as $prev) {
                    $copy = $path;
                    array_unshift($copy, $prev);
                    $paths[] = $copy;
                }
                unset($paths[$key]);
            }
        }
        return array_values($paths);
    }

    public function shortestPaths($source, $target, array $excluded = array())
    {
        $this->distance = array_fill_keys(array_keys($this->map), INF);
        $this->distance[$source] = 0;
        $this->prev = array_fill_keys(array_keys($this->map), []);
        $this->visited = [$source => 0];

        while (!empty($this->visited)) {
            $this->processQueue($excluded);
        }

        if ($source === $target) {
            return [[$source]];
        } elseif (empty($this->prev[$target])) {
            return [];
        }

        return $this->extractPaths($target);
    }
}