DAG.php
3.88 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
<?php
/**
* A Directed Acyclic Graph - used for doing topological sorts on dependencies, such as the before/after conditions
* in config yaml fragments
*
* @package framework
* @subpackage manifest
*/
class SS_DAG implements IteratorAggregate {
/**
* The nodes/vertices in the graph. Should be a numeric sequence of items (no string keys, no gaps).
* @var array|null
*/
protected $data;
/**
* The edges in the graph, in $to_idx => [$from_idx1, $from_idx2, ...] format
* @var array
*/
protected $dag;
public function __construct($data = null) {
$data = $data ? array_values($data) : array();
$this->data = $data;
$this->dag = array_fill_keys(array_keys($data), array());
}
/**
* Add another node/vertex
* @param $item anything - The item to add to the graph
*/
public function additem($item) {
$this->data[] = $item;
$this->dag[] = array();
}
/**
* Add an edge from one vertex to another.
*
* When passing actual nodes (as opposed to indexes), uses array_search with strict = true to find
*
* @param $from integer|any The index in $data of the node/vertex, or the node/vertex itself, that the edge
* goes from
* @param $to integer|any - The index in $data of the node/vertex, or the node/vertex itself, that the edge goes to
*/
public function addedge($from, $to) {
$i = is_numeric($from) ? $from : array_search($from, $this->data, true);
$j = is_numeric($to) ? $to : array_search($to, $this->data, true);
if ($i === false) throw new Exception("Couldnt find 'from' item in data when adding edge to DAG");
if ($j === false) throw new Exception("Couldnt find 'to' item in data when adding edge to DAG");
if (!isset($this->dag[$j])) $this->dag[$j] = array();
$this->dag[$j][] = $i;
}
/**
* Sort graph so that each node (a) comes before any nodes (b) where an edge exists from a to b
* @return array - The nodes
* @throws Exception - If the graph is cyclic (and so can't be sorted)
*/
public function sort() {
$data = $this->data; $dag = $this->dag; $sorted = array();
while (true) {
$withedges = array_filter($dag, 'count');
$starts = array_diff_key($dag, $withedges);
if (!count($starts)) break;
foreach ($starts as $i => $foo) $sorted[] = $data[$i];
foreach ($withedges as $j => $deps) {
$withedges[$j] = array_diff($withedges[$j], array_keys($starts));
}
$dag = $withedges;
}
if ($dag) {
$remainder = new SS_DAG($data); $remainder->dag = $dag;
throw new SS_DAG_CyclicException("DAG has cyclic requirements", $remainder);
}
return $sorted;
}
public function getIterator() {
return new SS_DAG_Iterator($this->data, $this->dag);
}
}
/**
* Exception thrown when the {@link SS_DAG} class is unable to resolve sorting the DAG due to cyclic dependencies.
*
* @package framework
* @subpackage manifest
*/
class SS_DAG_CyclicException extends Exception {
public $dag;
/**
* @param string $message The Exception message
* @param SS_DAG $dag The remainder of the Directed Acyclic Graph (DAG) after the last successful sort
*/
public function __construct($message, $dag) {
$this->dag = $dag;
parent::__construct($message);
}
}
/**
* @package framework
* @subpackage manifest
*/
class SS_DAG_Iterator implements Iterator {
protected $data;
protected $dag;
protected $dagkeys;
protected $i;
public function __construct($data, $dag) {
$this->data = $data;
$this->dag = $dag;
$this->rewind();
}
public function key() {
return $this->i;
}
public function current() {
$res = array();
$res['from'] = $this->data[$this->i];
$res['to'] = array();
foreach ($this->dag[$this->i] as $to) $res['to'][] = $this->data[$to];
return $res;
}
public function next() {
$this->i = array_shift($this->dagkeys);
}
public function rewind() {
$this->dagkeys = array_keys($this->dag);
$this->next();
}
public function valid() {
return $this->i !== null;
}
}