1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
namespace App\Component\Math\Graph\Path; |
4
|
|
|
|
5
|
|
|
/** |
6
|
|
|
* Dijikstra path search for weighted graph |
7
|
|
|
* |
8
|
|
|
*/ |
9
|
|
|
class Weight |
10
|
|
|
{ |
11
|
|
|
const _INF = 99999; |
12
|
|
|
|
13
|
|
|
/** |
14
|
|
|
* graph |
15
|
|
|
* |
16
|
|
|
* @var array |
17
|
|
|
*/ |
18
|
|
|
protected $graph; |
19
|
|
|
|
20
|
|
|
/** |
21
|
|
|
* source |
22
|
|
|
* |
23
|
|
|
* @var String |
24
|
|
|
*/ |
25
|
|
|
private $src; |
26
|
|
|
|
27
|
|
|
/** |
28
|
|
|
* destination |
29
|
|
|
* |
30
|
|
|
* @var String |
31
|
|
|
*/ |
32
|
|
|
private $dst; |
33
|
|
|
|
34
|
|
|
/** |
35
|
|
|
* path |
36
|
|
|
* |
37
|
|
|
* @var array |
38
|
|
|
*/ |
39
|
|
|
private $path = []; |
40
|
|
|
|
41
|
|
|
/** |
42
|
|
|
* the nearest path with its parent and weight |
43
|
|
|
* |
44
|
|
|
* @var array |
45
|
|
|
*/ |
46
|
|
|
private $s = []; |
47
|
|
|
|
48
|
|
|
/** |
49
|
|
|
* the left nodes without the nearest path |
50
|
|
|
* |
51
|
|
|
* @var array |
52
|
|
|
*/ |
53
|
|
|
private $q = []; |
54
|
|
|
|
55
|
|
|
/** |
56
|
|
|
* __construct |
57
|
|
|
* |
58
|
|
|
* @param array $graph |
59
|
|
|
*/ |
60
|
4 |
|
public function __construct($graph) |
61
|
|
|
{ |
62
|
4 |
|
$this->graph = $graph; |
63
|
|
|
} |
64
|
|
|
|
65
|
|
|
/** |
66
|
|
|
* path |
67
|
|
|
* |
68
|
|
|
* @param string $src |
69
|
|
|
* @param string $dst |
70
|
|
|
* @return array |
71
|
|
|
*/ |
72
|
1 |
|
public function path(string $src, string $dst): array |
73
|
|
|
{ |
74
|
1 |
|
$this->init($src, $dst); |
75
|
1 |
|
$this->path = []; |
76
|
1 |
|
if (isset($this->graph[$this->src]) && isset($this->graph[$this->dst])) { |
77
|
1 |
|
$this->search()->processPath(); |
78
|
|
|
} |
79
|
1 |
|
return $this->path; |
80
|
|
|
} |
81
|
|
|
|
82
|
|
|
/** |
83
|
|
|
* distance |
84
|
|
|
* |
85
|
|
|
* @return float |
86
|
|
|
*/ |
87
|
2 |
|
public function distance(): float |
88
|
|
|
{ |
89
|
2 |
|
return ($this->path) ? $this->s[$this->dst][1] : 0; |
90
|
|
|
} |
91
|
|
|
|
92
|
|
|
/** |
93
|
|
|
* start calculating |
94
|
|
|
* |
95
|
|
|
* @return Weight |
96
|
|
|
*/ |
97
|
1 |
|
protected function search(): Weight |
98
|
|
|
{ |
99
|
1 |
|
while (!empty($this->q)) { |
100
|
1 |
|
$min = $this->min(); |
101
|
1 |
|
if ($min == $this->dst) { |
102
|
1 |
|
break; |
103
|
|
|
} |
104
|
1 |
|
$keys = array_keys($this->graph[$min]); |
105
|
1 |
|
$kam = count($keys); |
106
|
1 |
|
for ($c = 0; $c < $kam; $c++) { |
107
|
1 |
|
$k = $keys[$c]; |
108
|
1 |
|
$v = $this->graph[$min][$k]; |
109
|
1 |
|
if (!empty($this->q[$k])) { |
110
|
1 |
|
if (($checkMin = $this->q[$min] + $v) < $this->q[$k]) { |
111
|
1 |
|
$this->q[$k] = $checkMin; |
112
|
1 |
|
$this->s[$k] = [$min, $this->q[$k]]; |
113
|
|
|
} |
114
|
|
|
} |
115
|
|
|
} |
116
|
1 |
|
unset($this->q[$min]); |
117
|
|
|
} |
118
|
1 |
|
return $this; |
119
|
|
|
} |
120
|
|
|
|
121
|
|
|
/** |
122
|
|
|
* lowest weighted node name |
123
|
|
|
* |
124
|
|
|
* @return string |
125
|
|
|
*/ |
126
|
1 |
|
protected function min(): string |
127
|
|
|
{ |
128
|
1 |
|
return array_search(min($this->q), $this->q); |
129
|
|
|
} |
130
|
|
|
|
131
|
|
|
/** |
132
|
|
|
* init queue assuming all edges are bi-directional |
133
|
|
|
* |
134
|
|
|
* @param string $src |
135
|
|
|
* @param string $dst |
136
|
|
|
* @return Weight |
137
|
|
|
*/ |
138
|
1 |
|
protected function init(string $src, string $dst): Weight |
139
|
|
|
{ |
140
|
1 |
|
$this->src = $src; |
141
|
1 |
|
$this->dst = $dst; |
142
|
1 |
|
$this->s = []; |
143
|
1 |
|
$this->q = []; |
144
|
1 |
|
$keys = array_keys($this->graph); |
145
|
1 |
|
foreach ($keys as $key) { |
146
|
1 |
|
$this->q[$key] = self::_INF; |
147
|
|
|
} |
148
|
1 |
|
$this->q[$this->src] = 0; |
149
|
1 |
|
return $this; |
150
|
|
|
} |
151
|
|
|
|
152
|
|
|
/** |
153
|
|
|
* set path |
154
|
|
|
* |
155
|
|
|
* @return Weight |
156
|
|
|
*/ |
157
|
1 |
|
protected function processPath(): Weight |
158
|
|
|
{ |
159
|
1 |
|
$this->path = []; |
160
|
1 |
|
$pos = $this->dst; |
161
|
1 |
|
while ($pos != $this->src) { |
162
|
1 |
|
$this->path[] = $pos; |
163
|
1 |
|
$pos = $this->s[$pos][0]; |
164
|
|
|
} |
165
|
1 |
|
$this->path[] = $this->src; |
166
|
1 |
|
$this->path = array_reverse($this->path); |
167
|
1 |
|
return $this; |
168
|
|
|
} |
169
|
|
|
} |
170
|
|
|
|