1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
/** |
4
|
|
|
* This class takes a directed graph and creates all possible paths starting form a single element. |
5
|
|
|
*/ |
6
|
|
|
namespace Rocket\Taxonomy\Utils; |
7
|
|
|
|
8
|
|
|
use CentralDesktop\Graph\Edge\DirectedEdge; |
9
|
|
|
use CentralDesktop\Graph\Graph\DirectedGraph; |
10
|
|
|
use CentralDesktop\Graph\Vertex; |
11
|
|
|
|
12
|
|
|
/** |
13
|
|
|
* Transforms a Directed Graph to a list of paths |
14
|
|
|
*/ |
15
|
|
|
class PathResolver |
16
|
|
|
{ |
17
|
|
|
/** |
18
|
|
|
* @var array The resolved paths |
19
|
|
|
*/ |
20
|
|
|
protected $paths; |
21
|
|
|
|
22
|
|
|
/** |
23
|
|
|
* @var array<integer> The path being prepared. |
24
|
|
|
*/ |
25
|
|
|
protected $current_path; |
26
|
|
|
|
27
|
|
|
/** |
28
|
|
|
* @var DirectedGraph The graph used to create the paths. |
29
|
|
|
*/ |
30
|
|
|
protected $digraph; |
31
|
|
|
|
32
|
|
|
/** |
33
|
|
|
* PathResolver constructor. |
34
|
|
|
* |
35
|
|
|
* @param DirectedGraph $graph The graph used to create the paths. |
36
|
|
|
*/ |
37
|
9 |
|
public function __construct(DirectedGraph $graph) |
38
|
|
|
{ |
39
|
9 |
|
$this->digraph = $graph; |
40
|
9 |
|
} |
41
|
|
|
|
42
|
|
|
/** |
43
|
|
|
* Resolve all paths that can be resolved from the start point. |
44
|
|
|
* |
45
|
|
|
* @param Vertex $start_vertex |
46
|
|
|
* @return array |
47
|
|
|
*/ |
48
|
9 |
|
public function resolvePaths(Vertex $start_vertex) |
49
|
|
|
{ |
50
|
9 |
|
$this->paths = []; |
51
|
|
|
|
52
|
|
|
/** |
53
|
|
|
* @var DirectedEdge |
54
|
|
|
*/ |
55
|
9 |
|
foreach ($start_vertex->incoming_edges as $edge) { |
56
|
9 |
|
$this->current_path = [$start_vertex->get_data()]; |
|
|
|
|
57
|
9 |
|
$this->getPathsRecursion($edge->get_source(), $edge); |
58
|
9 |
|
} |
59
|
|
|
|
60
|
9 |
|
return $this->paths; |
61
|
|
|
} |
62
|
|
|
|
63
|
|
|
/** |
64
|
|
|
* Recurse on all paths from the start point |
65
|
|
|
* |
66
|
|
|
* @param Vertex $start The Vertex to get started from |
67
|
|
|
* @param DirectedEdge $edge |
68
|
|
|
*/ |
69
|
9 |
|
protected function getPathsRecursion(Vertex $start, DirectedEdge $edge) |
70
|
|
|
{ |
71
|
|
|
// We don't want to visit the same vertex twice within a single path. (avoid loops) |
72
|
9 |
|
if (in_array($start->get_data(), $this->current_path)) { |
73
|
3 |
|
$this->paths[] = array_reverse($this->current_path); |
74
|
|
|
|
75
|
3 |
|
return; |
76
|
|
|
} |
77
|
|
|
|
78
|
9 |
|
$this->current_path[] = $start->get_data(); |
79
|
|
|
|
80
|
9 |
|
if ($start->incoming_edges->count() == 0) { |
81
|
6 |
|
$this->paths[] = array_reverse($this->current_path); |
82
|
|
|
|
83
|
6 |
|
return; |
84
|
|
|
} |
85
|
|
|
|
86
|
|
|
/** |
87
|
|
|
* @var DirectedEdge |
88
|
|
|
*/ |
89
|
5 |
|
foreach ($start->incoming_edges as $edge) { |
90
|
5 |
|
$this->getPathsRecursion($edge->get_source(), $edge); |
91
|
|
|
|
92
|
|
|
//remove the item that was added by the child |
93
|
5 |
|
array_pop($this->current_path); |
94
|
5 |
|
} |
95
|
5 |
|
} |
96
|
|
|
} |
97
|
|
|
|
Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property.
Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property..