Completed
Push — master ( 5a4ec5...1bffc6 )
by Benjamin
11:12 queued 05:47
created
src/Dijkstra.php 1 patch
Indentation   +123 added lines, -123 removed lines patch added patch discarded remove patch
@@ -4,116 +4,116 @@  discard block
 block discarded – undo
4 4
 
5 5
 class Dijkstra
6 6
 {
7
-    private $positions;
8
-    private $from;
9
-    private $to;
10
-    private $weights;
11
-    private $predecessors;
12
-
13
-    public function __construct(array $positions, Point $from, Point $to)
14
-    {
15
-        $this->positions = $positions;
16
-        $this->from = $from;
17
-        $this->to = $to;
18
-    }
19
-
20
-    public function findShortestPath(): array
21
-    {
22
-        $this->weights = [];
23
-        $this->predecessors = [];
24
-
25
-        foreach ($this->positions as $position) {
26
-            $weight = -1;
27
-            $passed = false;
28
-
29
-            if ($position->equals($this->from)) {
30
-                $weight = 0;
31
-                $passed = true;
32
-            }
33
-
34
-            // init weights array
35
-            $this->weights[$position->ref] = [
36
-                'position' => $position,
37
-                'weight' => $weight,
38
-                'passed' => $passed,
39
-            ];
40
-
41
-            // init predecessors array
42
-            $this->predecessors[$position->ref] = [
43
-                'position' => $position,
44
-                'previous' => null,
45
-            ];
46
-        }
47
-
48
-        return $this->run($this->from)->getPath();
49
-    }
50
-
51
-    protected function run(Point $parent): self
52
-    {
53
-        // we reached the final point !
54
-        if ($parent->equals($this->to)) {
55
-            return $this;
56
-        }
57
-
58
-        // we can set this node has been passed by
59
-        $this->weights[$parent->ref]['passed'] = true;
60
-
61
-        // search for weight between $parent and its children
62
-        foreach ($parent->points as $child) {
63
-            $this->calculateWeight($parent, $child);
64
-        }
65
-
66
-        // search for the next parent (smallest weight)
67
-        // we have to find the smallest weight for a node we didn't passed by atm
68
-        $smallest = INF;
69
-        $nextParent = null;
70
-        foreach ($this->weights as $weight) {
71
-            if ($weight['weight'] < $smallest && $weight['weight'] !== -1 && ! $weight['passed']) {
72
-                $smallest = $weight['weight'];
73
-                $nextParent = $weight['position'];
74
-            }
75
-        }
76
-        if (! is_null($nextParent)) {
77
-            return $this->run($nextParent);
78
-        }
79
-
80
-        return $this;
81
-    }
82
-
83
-    protected function getPath(): array
84
-    {
85
-        $path = [$this->to];
86
-
87
-        $point = $this->to;
88
-        while (true) {
89
-            foreach ($this->predecessors as $predecessor) {
90
-                if ($predecessor['position']->equals($point)) {
91
-                    $point = $predecessor['previous'];
92
-                    $path[] = $point;
93
-
94
-                    break;
95
-                }
96
-            }
97
-
98
-            // $point is null -> path impossible
99
-            if (is_null($point)) {
100
-                unset($path[count($path) - 1]);
101
-                break;
102
-            }
103
-
104
-            if ($point->equals($this->from)) {
105
-                break;
106
-            }
107
-        }
108
-
109
-        $path = array_reverse($path);
110
-
111
-        return $path;
112
-    }
113
-
114
-    protected function calculateWeight(Point $parent, Point $child): void
115
-    {
116
-        /*
7
+	private $positions;
8
+	private $from;
9
+	private $to;
10
+	private $weights;
11
+	private $predecessors;
12
+
13
+	public function __construct(array $positions, Point $from, Point $to)
14
+	{
15
+		$this->positions = $positions;
16
+		$this->from = $from;
17
+		$this->to = $to;
18
+	}
19
+
20
+	public function findShortestPath(): array
21
+	{
22
+		$this->weights = [];
23
+		$this->predecessors = [];
24
+
25
+		foreach ($this->positions as $position) {
26
+			$weight = -1;
27
+			$passed = false;
28
+
29
+			if ($position->equals($this->from)) {
30
+				$weight = 0;
31
+				$passed = true;
32
+			}
33
+
34
+			// init weights array
35
+			$this->weights[$position->ref] = [
36
+				'position' => $position,
37
+				'weight' => $weight,
38
+				'passed' => $passed,
39
+			];
40
+
41
+			// init predecessors array
42
+			$this->predecessors[$position->ref] = [
43
+				'position' => $position,
44
+				'previous' => null,
45
+			];
46
+		}
47
+
48
+		return $this->run($this->from)->getPath();
49
+	}
50
+
51
+	protected function run(Point $parent): self
52
+	{
53
+		// we reached the final point !
54
+		if ($parent->equals($this->to)) {
55
+			return $this;
56
+		}
57
+
58
+		// we can set this node has been passed by
59
+		$this->weights[$parent->ref]['passed'] = true;
60
+
61
+		// search for weight between $parent and its children
62
+		foreach ($parent->points as $child) {
63
+			$this->calculateWeight($parent, $child);
64
+		}
65
+
66
+		// search for the next parent (smallest weight)
67
+		// we have to find the smallest weight for a node we didn't passed by atm
68
+		$smallest = INF;
69
+		$nextParent = null;
70
+		foreach ($this->weights as $weight) {
71
+			if ($weight['weight'] < $smallest && $weight['weight'] !== -1 && ! $weight['passed']) {
72
+				$smallest = $weight['weight'];
73
+				$nextParent = $weight['position'];
74
+			}
75
+		}
76
+		if (! is_null($nextParent)) {
77
+			return $this->run($nextParent);
78
+		}
79
+
80
+		return $this;
81
+	}
82
+
83
+	protected function getPath(): array
84
+	{
85
+		$path = [$this->to];
86
+
87
+		$point = $this->to;
88
+		while (true) {
89
+			foreach ($this->predecessors as $predecessor) {
90
+				if ($predecessor['position']->equals($point)) {
91
+					$point = $predecessor['previous'];
92
+					$path[] = $point;
93
+
94
+					break;
95
+				}
96
+			}
97
+
98
+			// $point is null -> path impossible
99
+			if (is_null($point)) {
100
+				unset($path[count($path) - 1]);
101
+				break;
102
+			}
103
+
104
+			if ($point->equals($this->from)) {
105
+				break;
106
+			}
107
+		}
108
+
109
+		$path = array_reverse($path);
110
+
111
+		return $path;
112
+	}
113
+
114
+	protected function calculateWeight(Point $parent, Point $child): void
115
+	{
116
+		/*
117 117
          * Dijkstra algo says :
118 118
          *
119 119
          * IF (child-node is not traversed yet) AND
@@ -123,17 +123,17 @@  discard block
 block discarded – undo
123 123
          *  PREDECESSOR(child-node) = parent-node
124 124
          * ENDIF
125 125
          */
126
-        if (! $this->weights[$child->ref]['passed']
127
-            && ($this->weights[$parent->ref]['weight'] + self::distance($parent, $child) < $this->weights[$child->ref]['weight']
128
-                || $this->weights[$child->ref]['weight'] === -1)) {
129
-            $this->weights[$child->ref]['weight'] = $this->weights[$parent->ref]['weight'] + self::distance($parent, $child);
130
-            $this->predecessors[$child->ref]['previous'] = $parent;
131
-        }
132
-    }
133
-
134
-    public static function distance(Point $p1, Point $p2): float
135
-    {
136
-        // distance = square root of ((x2 - x1)^2 + (y2 - y1)^2)
137
-        return sqrt(bcpow($p2->x - $p1->x, 2) + bcpow($p2->y - $p1->y, 2));
138
-    }
126
+		if (! $this->weights[$child->ref]['passed']
127
+			&& ($this->weights[$parent->ref]['weight'] + self::distance($parent, $child) < $this->weights[$child->ref]['weight']
128
+				|| $this->weights[$child->ref]['weight'] === -1)) {
129
+			$this->weights[$child->ref]['weight'] = $this->weights[$parent->ref]['weight'] + self::distance($parent, $child);
130
+			$this->predecessors[$child->ref]['previous'] = $parent;
131
+		}
132
+	}
133
+
134
+	public static function distance(Point $p1, Point $p2): float
135
+	{
136
+		// distance = square root of ((x2 - x1)^2 + (y2 - y1)^2)
137
+		return sqrt(bcpow($p2->x - $p1->x, 2) + bcpow($p2->y - $p1->y, 2));
138
+	}
139 139
 }
Please login to merge, or discard this patch.