|
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
|
|
|
|
RocketPropelledTortoise /
Core
Loading history...
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..