MultiDijkstraPathfinder::operatingIn()   A
last analyzed

Complexity

Conditions 1
Paths 1

Size

Total Lines 3
Code Lines 1

Duplication

Lines 0
Ratio 0 %

Importance

Changes 1
Bugs 0 Features 0
Metric Value
eloc 1
c 1
b 0
f 0
dl 0
loc 3
rs 10
cc 1
nc 1
nop 1
1
<?php declare(strict_types=1);
2
3
namespace Stratadox\Pathfinder;
4
5
use function array_reverse;
6
use const INF;
7
use SplPriorityQueue;
8
use Stratadox\Pathfinder\Reconstruction\PathRetracer;
9
10
final class MultiDijkstraPathfinder implements MultiPathfinder
11
{
12
    private $network;
13
    private $path;
14
15
    private function __construct(Network $network)
16
    {
17
        $this->network = $network;
18
        $this->path = new PathRetracer();
19
    }
20
21
    public static function operatingIn(Network $graph): MultiPathfinder
22
    {
23
        return new self($graph);
24
    }
25
26
    public function from(string $start): array
27
    {
28
        return $this->shortestPaths($this->startingAt($start), $start);
29
    }
30
31
    private function shortestPaths(array $lastSteps, string $start): array
32
    {
33
        $paths = [];
34
        foreach ($lastSteps as $goal => $lastStep) {
35
            if ($goal !== $start) {
36
                $paths[$goal] = $this->path->retrace($start, $goal, $lastSteps);
37
            }
38
        }
39
        return $paths;
40
    }
41
42
    /** @throws NoPathAvailable */
43
    private function startingAt(string $start): array
44
    {
45
        if (!$this->network->has($start)) {
46
            throw NonExistingStart::tried($start);
47
        }
48
49
        $distanceTo = [$start => 0];
50
        $lastStepBefore = [];
51
52
        $underConsideration = new SplPriorityQueue();
53
        $underConsideration->insert($start, 0);
54
55
        while (!$underConsideration->isEmpty()) {
56
            $node = $underConsideration->top();
57
            $underConsideration->next();
58
59
            foreach ($this->network->neighboursOf($node) as $neighbour) {
60
                $alternativeCost = ($distanceTo[$node] ?? INF) +
61
                    $this->network->movementCostBetween($node, $neighbour);
62
63
                if ($alternativeCost < ($distanceTo[$neighbour] ?? INF)) {
64
                    $distanceTo[$neighbour] = $alternativeCost;
65
                    $lastStepBefore[$neighbour] = $node;
66
                    $underConsideration->insert($neighbour, -$alternativeCost);
67
                }
68
            }
69
        }
70
        return $lastStepBefore;
71
    }
72
}
73