Hoa central
Public Member Functions | Static Public Member Functions | Public Attributes | List of all members
Hoa\Graph\AdjacencyList Class Reference
Inheritance diagram for Hoa\Graph\AdjacencyList:

Public Member Functions

 __construct ($loop=parent::DISALLOW_LOOP)
 
 addNode (IGraph\Node $node, $parent=[])
 
 nodeExists ($nodeId)
 
 getNode ($nodeId)
 
 getParent ($nodeId)
 
 getChild ($nodeId)
 
 deleteNode ($nodeId, $propagate=parent::DELETE_RESTRICT)
 
 isLeaf ($nodeId)
 
 isRoot ($nodeId)
 
 __toString ()
 
- Public Member Functions inherited from Hoa\Graph\Graph
 addNode (IGraph\Node $node, $parent=[])
 
 nodeExists ($nodeId)
 
 getNode ($nodeId)
 
 getParent ($nodeId)
 
 getChild ($nodeId)
 
 deleteNode ($nodeId, $propagate=self::DELETE_RESTRICT)
 
 isLeaf ($nodeId)
 
 isRoot ($nodeId)
 
 allowLoop ($loop=self::DISALLOW_LOOP)
 
 isLoopAllow ()
 
 __toString ()
 

Static Public Member Functions

static getInstance ($type=parent::TYPE_ADJACENCYLIST)
 
- Static Public Member Functions inherited from Hoa\Graph\Graph
static getInstance ($type=self::TYPE_ADJACENCYLIST)
 

Public Attributes

const NODE_VALUE = 0
 
const NODE_CHILD = 1
 
- Public Attributes inherited from Hoa\Graph\Graph
const TYPE_ADJACENCYLIST = 'AdjacencyList'
 
const ALLOW_LOOP = true
 
const DISALLOW_LOOP = false
 
const DELETE_CASCADE = true
 
const DELETE_RESTRICT = false
 

Additional Inherited Members

- Protected Member Functions inherited from Hoa\Graph\Graph
 __construct ($loop=self::DISALLOW_LOOP)
 
 getNodes ()
 
- Protected Attributes inherited from Hoa\Graph\Graph
 $nodes = []
 
 $loop = self::DISALLOW_LOOP
 

Detailed Description

Class .

Code an adjacency list graph.

Definition at line 47 of file AdjacencyList.php.

Constructor & Destructor Documentation

Hoa\Graph\AdjacencyList::__construct (   $loop = parent::DISALLOW_LOOP)

Propagate the construction.

Parameters
bool$loopAllow or not loop.
Returns
void

Definition at line 71 of file AdjacencyList.php.

72  {
73  parent::__construct($loop);
74 
75  return;
76  }

Member Function Documentation

Hoa\Graph\AdjacencyList::__toString ( )

Print the graph in the DOT language.

Returns
string

Definition at line 348 of file AdjacencyList.php.

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  }

Here is the call graph for this function:

Hoa\Graph\AdjacencyList::addNode ( IGraph\Node  $node,
  $parent = [] 
)

Add a node.

Parameters
\Hoa\Graph\IGraph\Node$nodeNode to add.
mixed$parentParent of node.
Returns
void
Exceptions

Definition at line 101 of file AdjacencyList.php.

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  }

Here is the call graph for this function:

Hoa\Graph\AdjacencyList::deleteNode (   $nodeId,
  $propagate = parent::DELETE_RESTRICT 
)

Delete a node.

Parameters
mixed$nodeIdThe node ID or the node instance.
bool$propagatePropagate the erasure.
Returns
void
Exceptions

Definition at line 267 of file AdjacencyList.php.

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  }
deleteNode($nodeId, $propagate=parent::DELETE_RESTRICT)

Here is the call graph for this function:

Hoa\Graph\AdjacencyList::getChild (   $nodeId)

Get child of a specific node.

Parameters
mixed$nodeIdThe node ID or the node instance.
Returns
Exceptions

Definition at line 233 of file AdjacencyList.php.

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  }

Here is the call graph for this function:

Here is the caller graph for this function:

static Hoa\Graph\AdjacencyList::getInstance (   $type = parent::TYPE_ADJACENCYLIST)
static

Disallow to get a new instance.

Parameters
string$typeType of graph needed.
Returns
void
Exceptions

Definition at line 85 of file AdjacencyList.php.

86  {
87  throw new Exception(
88  'Cannot get a new from a typed graph.',
89  0
90  );
91  }
Hoa\Graph\AdjacencyList::getNode (   $nodeId)

Get a node.

Parameters
mixed$nodeIdThe node ID or the node instance.
Returns
object
Exceptions

Definition at line 172 of file AdjacencyList.php.

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  }

Here is the call graph for this function:

Here is the caller graph for this function:

Hoa\Graph\AdjacencyList::getParent (   $nodeId)

Get parent of a specific node.

Parameters
mixed$nodeIdThe node ID or the node instance.
Returns
Exceptions

Definition at line 192 of file AdjacencyList.php.

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  }

Here is the call graph for this function:

Here is the caller graph for this function:

Hoa\Graph\AdjacencyList::isLeaf (   $nodeId)

Whether node is a leaf, i.e. does not have any child.

Parameters
mixed$nodeIdThe node ID or the node instance.
Returns
bool
Exceptions

Definition at line 310 of file AdjacencyList.php.

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  }

Here is the call graph for this function:

Hoa\Graph\AdjacencyList::isRoot (   $nodeId)

Whether node is a root, i.e. does not have any parent.

Parameters
mixed$nodeIdThe node ID or the node instance.
Returns
bool
Exceptions

Definition at line 330 of file AdjacencyList.php.

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  }

Here is the call graph for this function:

Hoa\Graph\AdjacencyList::nodeExists (   $nodeId)

Check if a node does already exist or not.

Parameters
mixed$nodeIdThe node ID or the node instance.
Returns
bool

Definition at line 156 of file AdjacencyList.php.

157  {
158  if ($nodeId instanceof IGraph\Node) {
159  $nodeId = $nodeId->getNodeId();
160  }
161 
162  return isset($this->nodes[$nodeId]);
163  }

Here is the caller graph for this function:

Member Data Documentation

const Hoa\Graph\AdjacencyList::NODE_CHILD = 1

Node child index.

int

Definition at line 61 of file AdjacencyList.php.

const Hoa\Graph\AdjacencyList::NODE_VALUE = 0

Node value index.

int

Definition at line 54 of file AdjacencyList.php.


The documentation for this class was generated from the following file: