Hoa central
AdjacencyList.php
Go to the documentation of this file.
1 <?php
2 
37 namespace Hoa\Graph;
38 
47 class AdjacencyList extends Graph
48 {
54  const NODE_VALUE = 0;
55 
61  const NODE_CHILD = 1;
62 
63 
64 
71  public function __construct($loop = parent::DISALLOW_LOOP)
72  {
73  parent::__construct($loop);
74 
75  return;
76  }
77 
85  public static function getInstance($type = parent::TYPE_ADJACENCYLIST)
86  {
87  throw new Exception(
88  'Cannot get a new from a typed graph.',
89  0
90  );
91  }
92 
101  public function addNode(IGraph\Node $node, $parent = [])
102  {
103  if (!is_array($parent)) {
104  $parent = [$parent];
105  }
106 
107  if (parent::DISALLOW_LOOP === $this->isLoopAllow()) {
108  if (true === $this->nodeExists($node->getNodeId())) {
109  throw new Exception(
110  'Node %s already exists.',
111  1,
112  $node->getNodeId()
113  );
114  }
115 
116  if (in_array($node->getNodeId(), $parent)) {
117  throw new Exception(
118  'Node %s cannot define itself in parent.',
119  2,
120  $node->getNodeId()
121  );
122  }
123  }
124 
125  $this->nodes[$node->getNodeId()][self::NODE_VALUE] = $node;
126 
127  if (!isset($this->nodes[$node->getNodeId()][self::NODE_CHILD])) {
128  $this->nodes[$node->getNodeId()][self::NODE_CHILD] = [];
129  }
130 
131  foreach ($parent as $foo => $nodeId) {
132  if ($nodeId instanceof IGraph\Node) {
133  $nodeId = $nodeId->getNodeId();
134  }
135 
136  if (parent::DISALLOW_LOOP === $this->isLoopAllow()) {
137  if (false === $this->nodeExists($nodeId)) {
138  throw new Exception(
139  'Node %s does not exist.',
140  3,
141  $nodeId
142  );
143  }
144  }
145 
146  $this->nodes[$nodeId][self::NODE_CHILD][] = $node->getNodeId();
147  }
148  }
149 
156  public function nodeExists($nodeId)
157  {
158  if ($nodeId instanceof IGraph\Node) {
159  $nodeId = $nodeId->getNodeId();
160  }
161 
162  return isset($this->nodes[$nodeId]);
163  }
164 
172  public function getNode($nodeId)
173  {
174  if ($nodeId instanceof IGraph\Node) {
175  $nodeId = $nodeId->getNodeId();
176  }
177 
178  if (false === $this->nodeExists($nodeId)) {
179  throw new Exception('Node %s does not exist.', 4, $nodeId);
180  }
181 
182  return $this->nodes[$nodeId][self::NODE_VALUE];
183  }
184 
192  public function getParent($nodeId)
193  {
194  if ($nodeId instanceof IGraph\Node) {
195  $nodeId = $nodeId->getNodeId();
196  }
197 
198  if (false === $this->nodeExists($nodeId)) {
199  throw new Exception('Node %s does not exist.', 5, $nodeId);
200  }
201 
202  $parent = new \ArrayObject(
203  [],
204  \ArrayObject::ARRAY_AS_PROPS,
205  'ArrayIterator'
206  );
207 
208  foreach ($this->getNodes() as $id => $values) {
209  if (parent::DISALLOW_LOOP === $this->isLoopAllow()) {
210  if ($nodeId == $id) {
211  continue;
212  }
213  }
214 
215  if (in_array($nodeId, $values[self::NODE_CHILD])) {
216  $parent->offsetSet(
217  $id,
218  $this->getNode($id)
219  );
220  }
221  }
222 
223  return $parent;
224  }
225 
233  public function getChild($nodeId)
234  {
235  if ($nodeId instanceof IGraph\Node) {
236  $nodeId = $nodeId->getNodeId();
237  }
238 
239  if (false === $this->nodeExists($nodeId)) {
240  throw new Exception('Node %s does not exist.', 6, $nodeId);
241  }
242 
243  $child = new \ArrayObject(
244  [],
245  \ArrayObject::ARRAY_AS_PROPS,
246  'ArrayIterator'
247  );
248 
249  foreach ($this->nodes[$nodeId][self::NODE_CHILD] as $foo => $id) {
250  $child->offsetSet(
251  $id,
252  $this->getNode($id)
253  );
254  }
255 
256  return $child;
257  }
258 
267  public function deleteNode($nodeId, $propagate = parent::DELETE_RESTRICT)
268  {
269  if ($nodeId instanceof IGraph\Node) {
270  $nodeId = $nodeId->getNodeId();
271  }
272 
273  if (false === $this->nodeExists($nodeId)) {
274  return;
275  }
276 
277  if ($propagate == parent::DELETE_RESTRICT) {
278  if (empty($this->nodes[$nodeId][self::NODE_CHILD])) {
279  unset($this->nodes[$nodeId]);
280 
281  foreach ($this->getNodes() as $id => $values) {
282  if (false !== $key = array_search($nodeId, $values[self::NODE_CHILD])) {
283  unset($this->nodes[$id][self::NODE_CHILD][$key]);
284  }
285  }
286  } else {
287  throw new Exception(
288  'Cannot delete %s node in restrict delete mode, because ' .
289  'it has one or more children.',
290  7,
291  $nodeId
292  );
293  }
294  } else {
295  foreach ($this->nodes[$nodeId][self::NODE_CHILD] as $foo => $id) {
296  $this->deleteNode($id, $propagate);
297  }
298 
299  $this->deleteNode($nodeId, parent::DELETE_RESTRICT);
300  }
301  }
302 
310  public function isLeaf($nodeId)
311  {
312  if ($nodeId instanceof IGraph\Node) {
313  $nodeId = $nodeId->getNodeId();
314  }
315 
316  if (false === $this->nodeExists($nodeId)) {
317  throw new Exception('Node %s does not exist.', 8, $nodeId);
318  }
319 
320  return empty($this->nodes[$nodeId][self::NODE_CHILD]);
321  }
322 
330  public function isRoot($nodeId)
331  {
332  if ($nodeId instanceof IGraph\Node) {
333  $nodeId = $nodeId->getNodeId();
334  }
335 
336  if (false === $this->nodeExists($nodeId)) {
337  throw new Exception('Node %s does not exist.', 9, $nodeId);
338  }
339 
340  return count($this->getParent($nodeId)) == 0;
341  }
342 
348  public function __toString()
349  {
350  $out = 'digraph {' . "\n";
351 
352  foreach ($this->getNodes() as $nodeId => $foo) {
353  $out .= ' ' . $nodeId . ';' . "\n";
354  }
355 
356  foreach ($this->getNodes() as $nodeId => $foo) {
357  foreach ($this->getChild($nodeId) as $fooo => $child) {
358  $out .=
359  ' ' . $nodeId . ' -> ' .
360  $child->getNodeId() . ';' . "\n";
361  }
362  }
363 
364  $out .= '}';
365 
366  return $out;
367  }
368 }
static getInstance($type=parent::TYPE_ADJACENCYLIST)
__construct($loop=parent::DISALLOW_LOOP)
deleteNode($nodeId, $propagate=parent::DELETE_RESTRICT)
addNode(IGraph\Node $node, $parent=[])