1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
namespace Graphp\Path; |
4
|
|
|
|
5
|
|
|
use ArrayObject; |
6
|
|
|
use InvalidArgumentException; |
7
|
|
|
use Graphp\GraphInterface; |
8
|
|
|
use Graphp\GraphPathInterface; |
9
|
|
|
use Graphp\GraphUtils; |
10
|
|
|
use Graphp\Vertex\VertexInterface; |
11
|
|
|
|
12
|
|
|
/** |
13
|
|
|
* Class GraphWalk |
14
|
|
|
* |
15
|
|
|
* @package Graphp\Path |
16
|
|
|
*/ |
17
|
|
|
class GraphWalk extends AbstractGraphPath |
18
|
|
|
{ |
19
|
|
|
/** |
20
|
|
|
* The edge list making up the path |
21
|
|
|
* |
22
|
|
|
* @var array |
23
|
|
|
*/ |
24
|
|
|
protected $edgeList; |
25
|
|
|
|
26
|
|
|
/** |
27
|
|
|
* The vertex list making up the path |
28
|
|
|
* |
29
|
|
|
* @var array |
30
|
|
|
*/ |
31
|
|
|
protected $vertexList; |
32
|
|
|
|
33
|
|
|
/** |
34
|
|
|
* The walk unique hash |
35
|
|
|
* |
36
|
|
|
* @var string |
37
|
|
|
*/ |
38
|
|
|
private $hash; |
39
|
|
|
|
40
|
|
|
/** |
41
|
|
|
* Construct a new graph walk |
42
|
|
|
* |
43
|
|
|
* @param GraphPathInterface $other - the other walk |
44
|
|
|
* |
45
|
|
|
* @throws InvalidArgumentException |
46
|
|
|
*/ |
47
|
19 |
|
public function __construct( |
48
|
|
|
GraphInterface $graph, |
49
|
|
|
?VertexInterface $startVertex = null, |
50
|
|
|
?VertexInterface $endVertex = null, |
51
|
|
|
?array $vertexList = null, |
52
|
|
|
?array $edgeList = null, |
53
|
|
|
?float $weight = 0.0 |
54
|
|
|
) { |
55
|
19 |
|
if (is_null($vertexList) && is_null($edgeList)) { |
56
|
1 |
|
throw new InvalidArgumentException("Vertex list and edge list cannot both be empty!"); |
57
|
|
|
} |
58
|
|
|
|
59
|
|
|
if ( |
60
|
18 |
|
!is_null($startVertex) |
61
|
18 |
|
&& !is_null($vertexList) |
62
|
18 |
|
&& !is_null($edgeList) |
63
|
18 |
|
&& (count($edgeList) + 1 != count($vertexList)) |
64
|
|
|
) { |
65
|
|
|
throw new InvalidArgumentException( |
66
|
|
|
"VertexList and edgeList do not correspond to the same path (cardinality of vertexList +1 " . |
67
|
|
|
"must equal the cardinality of the edgeList)" |
68
|
|
|
); |
69
|
|
|
} |
70
|
|
|
|
71
|
18 |
|
$this->graph = $graph; |
72
|
18 |
|
$this->startVertex = $startVertex; |
73
|
18 |
|
$this->endVertex = $endVertex; |
74
|
18 |
|
$this->weight = $weight; |
75
|
18 |
|
$this->vertexList = $vertexList; |
76
|
18 |
|
$this->edgeList = $edgeList; |
77
|
18 |
|
$this->hash = $this->isEmpty() ? 1 : uniqid('', true); |
78
|
18 |
|
} |
79
|
|
|
|
80
|
|
|
/** |
81
|
|
|
* Get the edges making up the path |
82
|
|
|
* |
83
|
|
|
* @return array |
84
|
|
|
*/ |
85
|
8 |
|
public function getEdgeList(): array |
86
|
|
|
{ |
87
|
8 |
|
return !is_null($this->edgeList) ? $this->edgeList : parent::getEdgeList(); |
|
|
|
|
88
|
|
|
} |
89
|
|
|
|
90
|
|
|
/** |
91
|
|
|
* Get the vertices making up the path |
92
|
|
|
* |
93
|
|
|
* @return array |
94
|
|
|
*/ |
95
|
6 |
|
public function getVertexList(): array |
96
|
|
|
{ |
97
|
6 |
|
return !is_null($this->vertexList) ? $this->vertexList : parent::getVertexList(); |
|
|
|
|
98
|
|
|
} |
99
|
|
|
|
100
|
|
|
/** |
101
|
|
|
* Get the length of the path |
102
|
|
|
* |
103
|
|
|
* @return int |
104
|
|
|
*/ |
105
|
1 |
|
public function getLength(): int |
106
|
|
|
{ |
107
|
1 |
|
if (!is_null($this->edgeList)) { |
|
|
|
|
108
|
1 |
|
return count($this->edgeList); |
109
|
|
|
} |
110
|
|
|
|
111
|
|
|
if (!is_null($this->vertexList)) { |
112
|
|
|
return count($this->vertexList) - 1; |
113
|
|
|
} |
114
|
|
|
|
115
|
|
|
return 0; |
116
|
|
|
} |
117
|
|
|
|
118
|
|
|
/** |
119
|
|
|
* Reverse the direction of the walk |
120
|
|
|
* |
121
|
|
|
* @return GraphPathInterface |
122
|
|
|
* |
123
|
|
|
* @throws InvalidArgumentException |
124
|
|
|
*/ |
125
|
3 |
|
public function reverse(): GraphPathInterface |
126
|
|
|
{ |
127
|
3 |
|
$revVertexList = null; |
128
|
3 |
|
$revEdgeList = null; |
129
|
3 |
|
$revWeight = 0; |
130
|
|
|
|
131
|
3 |
|
if (!empty($this->vertexList)) { |
132
|
3 |
|
$revVertexList = array_reverse($this->vertexList); |
133
|
3 |
|
if ($this->graph->getType()->isUndirected()) { |
134
|
1 |
|
$revWeight = $this->weight; |
135
|
|
|
} |
136
|
|
|
|
137
|
|
|
// Check validity of the path. |
138
|
3 |
|
if (!$this->graph->getType()->isUndirected() && empty($this->edgeList)) { |
139
|
2 |
|
for ($i = 0; $i < count($revVertexList) - 1; $i += 1) { |
140
|
2 |
|
$sourceVertex = $revVertexList[$i]; |
141
|
2 |
|
$targetVertex = $revVertexList[$i + 1]; |
142
|
2 |
|
$edge = $this->graph->getEdge($sourceVertex, $targetVertex); |
143
|
2 |
|
if (is_null($edge)) { |
144
|
1 |
|
throw new InvalidArgumentException( |
145
|
|
|
"this walk cannot be reversed. The graph does not contain a reverse arc for arc " |
146
|
1 |
|
. (string) $this->graph->getEdge($targetVertex, $sourceVertex) |
147
|
|
|
); |
148
|
|
|
} else { |
149
|
1 |
|
$revWeight += $this->graph->getEdgeWeight($edge); |
150
|
|
|
} |
151
|
|
|
} |
152
|
|
|
} |
153
|
|
|
} |
154
|
|
|
|
155
|
2 |
|
if (!empty($this->edgeList)) { |
156
|
1 |
|
if ($this->graph->getType()->isUndirected()) { |
157
|
1 |
|
$revEdgeList = array_reverse($this->edgeList); |
158
|
1 |
|
$revWeight = $this->weight; |
159
|
|
|
} else { |
160
|
|
|
$revEdgeList = []; |
161
|
|
|
$edgeIterator = (new ArrayObject(array_reverse($this->edgeList)))->getIterator(); |
162
|
|
|
while ($edgeIterator->valid()) { |
163
|
|
|
$edge = $edgeIterator->current(); |
164
|
|
|
$sourceVertex = $this->graph->getEdgeSource($edge); |
165
|
|
|
$targetVertex = $this->graph->getEdgeTarget($edge); |
166
|
|
|
$revEdge = $this->graph->getEdge($targetVertex, $sourceVertex); |
167
|
|
|
if (is_null($revEdge)) { |
168
|
|
|
throw new InvalidArgumentException( |
169
|
|
|
"this walk cannot be reversed. The graph does not contain a reverse arc for arc " . |
170
|
|
|
(string) $edge |
171
|
|
|
); |
172
|
|
|
} |
173
|
|
|
$revEdgeList[] = $revEdge; |
174
|
|
|
$revWeight += $this->graph->getEdgeWeight($revEdge); |
175
|
|
|
$edgeIterator->next(); |
176
|
|
|
} |
177
|
|
|
} |
178
|
|
|
} |
179
|
2 |
|
$gw = new GraphWalk( |
180
|
2 |
|
$this->graph, |
181
|
2 |
|
$this->endVertex, |
182
|
2 |
|
$this->startVertex, |
183
|
2 |
|
$revVertexList, |
184
|
2 |
|
$revEdgeList, |
185
|
2 |
|
$revWeight |
186
|
|
|
); |
187
|
2 |
|
return $gw; |
188
|
|
|
} |
189
|
|
|
|
190
|
|
|
/** |
191
|
|
|
* Concatenate the specified GraphWalk to the end of this GraphWalk |
192
|
|
|
* |
193
|
|
|
* @param GraphPathInterface $extension - the graph walk |
194
|
|
|
* |
195
|
|
|
* @return GraphPathInterface |
196
|
|
|
*/ |
197
|
4 |
|
public function concat(GraphPathInterface $extension): GraphPathInterface |
198
|
|
|
{ |
199
|
4 |
|
if ($this->isEmpty()) { |
200
|
1 |
|
throw new InvalidArgumentException("An empty path cannot be extended"); |
201
|
|
|
} |
202
|
3 |
|
if (!$this->endVertex->equals($extension->getStartVertex())) { |
203
|
1 |
|
throw new InvalidArgumentException( |
204
|
|
|
"This path can only be extended by another path if the end vertex of the " . |
205
|
1 |
|
"orginal path and the start vertex of the extension are equal." |
206
|
|
|
); |
207
|
|
|
} |
208
|
|
|
|
209
|
2 |
|
$concatVertexList = null; |
210
|
2 |
|
$concatEdgeList = null; |
211
|
|
|
|
212
|
2 |
|
if (!is_null($this->vertexList)) { |
|
|
|
|
213
|
2 |
|
$concatVertexList = array_merge($this->vertexList, array_slice($extension->getVertexList() ?? [], 1)); |
214
|
|
|
} |
215
|
|
|
|
216
|
2 |
|
if (!is_null($this->edgeList)) { |
|
|
|
|
217
|
|
|
$concatEdgeList = array_merge($this->edgeList, array_slice($extension->getEdgeList() ?? [], 1)); |
218
|
|
|
} |
219
|
|
|
|
220
|
2 |
|
$gw = new GraphWalk( |
221
|
2 |
|
$this->graph, |
222
|
2 |
|
$this->startVertex, |
223
|
2 |
|
$extension->getEndVertex(), |
224
|
2 |
|
$concatVertexList, |
225
|
2 |
|
$concatEdgeList, |
226
|
2 |
|
$this->weight + $extension->getWeight() |
227
|
|
|
); |
228
|
2 |
|
return $gw; |
229
|
|
|
} |
230
|
|
|
|
231
|
|
|
/** |
232
|
|
|
* Verify that the given path is feasible |
233
|
|
|
* |
234
|
|
|
* @return bool |
235
|
|
|
* |
236
|
|
|
* @throws InvalidArgumentException |
237
|
|
|
*/ |
238
|
8 |
|
public function verify(): bool |
239
|
|
|
{ |
240
|
8 |
|
if ($this->isEmpty()) { |
241
|
1 |
|
return true; |
242
|
|
|
} |
243
|
|
|
|
244
|
8 |
|
if (!empty($this->vertexList)) { |
245
|
7 |
|
if (!$this->startVertex->equals($this->vertexList[0])) { |
246
|
|
|
throw new InvalidArgumentException( |
247
|
|
|
"The start vertex must be the first vertex in the vertex list" |
248
|
|
|
); |
249
|
|
|
} |
250
|
7 |
|
if (!$this->endVertex->equals($this->vertexList[count($this->vertexList) - 1])) { |
251
|
|
|
throw new InvalidArgumentException( |
252
|
|
|
"The end vertex must be the last vertex in the vertex list" |
253
|
|
|
); |
254
|
|
|
} |
255
|
|
|
// All vertices and edges in the path must be contained in the graph |
256
|
7 |
|
if (count(array_diff($this->vertexList, $this->graph->vertexSet()->getArrayCopy())) >= 1) { |
257
|
|
|
throw new InvalidArgumentException( |
258
|
|
|
"Not all vertices in the path are contained in the graph" |
259
|
|
|
); |
260
|
|
|
} |
261
|
|
|
|
262
|
7 |
|
if (empty($this->edgeList)) { |
263
|
|
|
// Verify sequence |
264
|
7 |
|
$vertexIterator = (new ArrayObject($this->vertexList))->getIterator(); |
265
|
7 |
|
$sourceVertex = $vertexIterator->current(); |
266
|
7 |
|
$vertexIterator->next(); |
267
|
7 |
|
while ($vertexIterator->valid()) { |
268
|
6 |
|
$targetVertex = $vertexIterator->current(); |
269
|
6 |
|
if (is_null($this->graph->getEdge($sourceVertex, $targetVertex))) { |
270
|
2 |
|
throw new InvalidArgumentException( |
271
|
|
|
"The vertexList does not constitute to a feasible path. Edge (" . |
272
|
2 |
|
(string) $sourceVertex . "," . (string) $targetVertex . ") does not exist in the graph." |
273
|
|
|
); |
274
|
|
|
} |
275
|
5 |
|
$vertexIterator->next(); |
276
|
5 |
|
$sourceVertex = $targetVertex; |
277
|
|
|
} |
278
|
|
|
} |
279
|
|
|
} |
280
|
|
|
|
281
|
6 |
|
if (!empty($this->edgeList)) { |
282
|
2 |
|
if (!GraphUtils::testIncidence($this->graph, $this->edgeList[0], $this->startVertex)) { |
283
|
|
|
throw new InvalidArgumentException( |
284
|
|
|
"The first edge in the edge list must leave the start vertex" |
285
|
|
|
); |
286
|
|
|
} |
287
|
2 |
|
if (count(array_diff($this->edgeList, $this->graph->edgeSet()->getArrayCopy())) >= 1) { |
288
|
|
|
throw new InvalidArgumentException( |
289
|
|
|
"Not all edges in the path are contained in the graph" |
290
|
|
|
); |
291
|
|
|
} |
292
|
|
|
|
293
|
2 |
|
if (empty($this->vertexList)) { |
294
|
2 |
|
$vertex = $this->startVertex; |
295
|
2 |
|
foreach ($this->edgeList as $edge) { |
296
|
2 |
|
if (!GraphUtils::testIncidence($this->graph, $edge, $vertex)) { |
297
|
1 |
|
throw new InvalidArgumentException( |
298
|
|
|
"The edgeList does not constitute to a feasible path. Conflicting edge: " . |
299
|
1 |
|
(string) $edge |
300
|
|
|
); |
301
|
|
|
} |
302
|
2 |
|
$vertex = GraphUtils::getOppositeVertex($this->graph, $edge, $vertex); |
303
|
|
|
} |
304
|
1 |
|
if (!$vertex->equals($this->endVertex)) { |
305
|
|
|
throw new InvalidArgumentException( |
306
|
|
|
"The path defined by the edgeList does not end in the endVertex." |
307
|
|
|
); |
308
|
|
|
} |
309
|
|
|
} |
310
|
|
|
} |
311
|
|
|
|
312
|
5 |
|
if (!empty($this->vertexList) && !empty($this->edgeList)) { |
313
|
|
|
// Verify that the path is an actual path in the graph |
314
|
|
|
if (count($this->edgeList) + 1 != count($this->vertexList)) { |
315
|
|
|
throw new InvalidArgumentException( |
316
|
|
|
"VertexList and edgeList do not correspond to the same path (cardinality of " . |
317
|
|
|
"vertexList +1 must equal the cardinality of the edgeList)" |
318
|
|
|
); |
319
|
|
|
} |
320
|
|
|
|
321
|
|
|
$len = count($this->vertexList) - 1; |
322
|
|
|
$edges = $this->getEdgeList(); |
323
|
|
|
for ($i = 0; $i < $len; $i += 1) { |
324
|
|
|
$startVertex = $this->vertexList[$i]; |
325
|
|
|
$endVertex = $this->vertexList[$i + 1]; |
326
|
|
|
$edge = $edges[$i]; |
327
|
|
|
|
328
|
|
|
if ($this->graph->getType()->isDirected()) { |
329
|
|
|
if ( |
330
|
|
|
!$this->graph->getEdgeSource($edge)->equals($startVertex) |
331
|
|
|
|| !$this->graph->getEdgeTarget($edge)->equals($endVertex) |
332
|
|
|
) { |
333
|
|
|
throw new InvalidArgumentException( |
334
|
|
|
"VertexList and edgeList do not form a feasible path" |
335
|
|
|
); |
336
|
|
|
} |
337
|
|
|
} else { |
338
|
|
|
if ( |
339
|
|
|
!GraphUtils::testIncidence($this->graph, $edge, $startVertex) |
340
|
|
|
|| !GraphUtils::getOppositeVertex($this->graph, $edge, $startVertex)->equals($endVertex) |
341
|
|
|
) { |
342
|
|
|
throw new InvalidArgumentException( |
343
|
|
|
"VertexList and edgeList do not form a feasible path" |
344
|
|
|
); |
345
|
|
|
} |
346
|
|
|
} |
347
|
|
|
} |
348
|
|
|
} |
349
|
|
|
|
350
|
5 |
|
return true; |
351
|
|
|
} |
352
|
|
|
|
353
|
|
|
/** |
354
|
|
|
* Create an empty walk |
355
|
|
|
* |
356
|
|
|
* @param GraphInterface $graph - the graph |
357
|
|
|
* |
358
|
|
|
* @return GraphPathInterface |
359
|
|
|
*/ |
360
|
2 |
|
public static function emptyWalk(GraphInterface $graph): GraphPathInterface |
361
|
|
|
{ |
362
|
2 |
|
return new GraphWalk($graph, null, null, [], [], 0.0); |
363
|
|
|
} |
364
|
|
|
|
365
|
|
|
/** |
366
|
|
|
* Create a walk consisting of one vertex |
367
|
|
|
* |
368
|
|
|
* @param GraphInterface $graph - the graph |
369
|
|
|
* @param VertexInterface $vertex - the vertex |
370
|
|
|
* @param float $weight - the weight |
371
|
|
|
* |
372
|
|
|
* @return GraphPathInterface |
373
|
|
|
*/ |
374
|
6 |
|
public static function singletonWalk( |
375
|
|
|
GraphInterface $graph, |
376
|
|
|
VertexInterface $vertex, |
377
|
|
|
?float $weight = 0.0 |
378
|
|
|
): GraphPathInterface { |
379
|
6 |
|
return new GraphWalk( |
380
|
6 |
|
$graph, |
381
|
6 |
|
$vertex, |
382
|
6 |
|
$vertex, |
383
|
6 |
|
[$vertex], |
384
|
6 |
|
[], |
385
|
6 |
|
$weight |
386
|
|
|
); |
387
|
|
|
} |
388
|
|
|
|
389
|
|
|
/** |
390
|
|
|
* Get the path string representation |
391
|
|
|
* |
392
|
|
|
* @return string |
393
|
|
|
*/ |
394
|
|
|
public function __toString(): string |
395
|
|
|
{ |
396
|
|
|
if (!empty($this->vertexList)) { |
397
|
|
|
return implode('', array_map(function ($vertex) { |
398
|
|
|
return (string) $vertex; |
399
|
|
|
}, $this->vertexList)); |
400
|
|
|
} |
401
|
|
|
|
402
|
|
|
if (!empty($this->edgeList)) { |
403
|
|
|
return implode('', array_map(function ($edge) { |
404
|
|
|
return (string) $edge; |
405
|
|
|
}, $this->edgeList)); |
406
|
|
|
} |
407
|
|
|
|
408
|
|
|
return ''; |
409
|
|
|
} |
410
|
|
|
|
411
|
|
|
/** |
412
|
|
|
* Check if two walks are equal |
413
|
|
|
* |
414
|
|
|
* @param GraphPathInterface $other - the other walk |
415
|
|
|
*/ |
416
|
4 |
|
public function equals(GraphPathInterface $other): bool |
417
|
|
|
{ |
418
|
4 |
|
if ($this->hash == $other->getHash()) { |
|
|
|
|
419
|
|
|
return true; |
420
|
|
|
} |
421
|
|
|
|
422
|
4 |
|
if ($this->isEmpty() && $other->isEmpty()) { |
|
|
|
|
423
|
|
|
return true; |
424
|
|
|
} |
425
|
|
|
|
426
|
4 |
|
if ($this->isEmpty()) { |
427
|
|
|
return false; |
428
|
|
|
} |
429
|
|
|
|
430
|
|
|
if ( |
431
|
4 |
|
!$this->startVertex->equals($other->getStartVertex()) |
432
|
4 |
|
|| !$this->endVertex->equals($other->getEndVertex()) |
433
|
|
|
) { |
434
|
|
|
return false; |
435
|
|
|
} |
436
|
|
|
|
437
|
4 |
|
if (empty($this->edgeList) && !$other->getGraph()->getType()->isAllowingMultipleEdges()) { |
438
|
2 |
|
return $this->vertexList == $other->getVertexList(); |
439
|
|
|
} |
440
|
2 |
|
return $this->edgeList == $other->getEdgeList(); |
441
|
|
|
} |
442
|
|
|
|
443
|
|
|
/** |
444
|
|
|
* Get the walk hash |
445
|
|
|
* |
446
|
|
|
* @return string |
447
|
|
|
*/ |
448
|
4 |
|
public function getHash(): string |
449
|
|
|
{ |
450
|
4 |
|
return $this->hash; |
451
|
|
|
} |
452
|
|
|
|
453
|
|
|
/** |
454
|
|
|
* Check if the path is empty |
455
|
|
|
* |
456
|
|
|
* @return bool |
457
|
|
|
*/ |
458
|
18 |
|
public function isEmpty(): bool |
459
|
|
|
{ |
460
|
18 |
|
return is_null($this->startVertex); |
461
|
|
|
} |
462
|
|
|
} |
463
|
|
|
|