DependencyOrderingService Class Reference

Public Member Functions
	orderByDependencies (array $items, $beforeKey= 'before', $afterKey= 'after')
	calculateOrder (array $dependencyGraph)
	findRootIds (array $dependencyGraph)

Protected Member Functions
	getIncomingEdgeCount (array $dependencyGraph, $identifier)
	findPathInGraph (array $graph, $from, $to)
	prepareDependencies (array $dependencies, $beforeKey= 'before', $afterKey= 'after')

Detailed Description

This class provides functionality to build an ordered list from a set of dependencies.

We use an adjacency matrix for the dependency graph (DAG)

Example structure of the DAG is: A => (A => FALSE, B => TRUE, C => FALSE) B => (A => FALSE, B => FALSE, C => FALSE) C => (A => TRUE, B => FALSE, C => FALSE)

A depends on B, C depends on A, B is independent

Definition at line 30 of file DependencyOrderingService.php.

Member Function Documentation

calculateOrder

(

array

$dependencyGraph

)

Calculate an ordered list for a dependencyGraph

Parameters

bool[][]

$dependencyGraph

Returns

mixed[] Sorted array of keys of $dependencies

Exceptions

\UnexpectedValueException

Definition at line 132 of file DependencyOrderingService.php.

References DependencyOrderingService\findRootIds(), and DependencyOrderingService\getIncomingEdgeCount().

Referenced by DependencyOrderingService\orderByDependencies().

findPathInGraph ( array  $graph,   $from,   $to  )

protected

Find any path in the graph from given start node to destination node

Parameters

array	$graph	Directed graph
string	$from	Start node
string	$to	Destination node

Returns

array Nodes of the found path; empty if no path is found

Definition at line 238 of file DependencyOrderingService.php.

findRootIds

(

array

$dependencyGraph

)

Find all root nodes of a graph

Root nodes are those, where nothing else depends on (they can be the last in the loading order). If there are no dependencies at all, all nodes are root nodes.

Parameters

bool[][]

$dependencyGraph

Returns

array List of identifiers which are root nodes

Definition at line 218 of file DependencyOrderingService.php.

References DependencyOrderingService\getIncomingEdgeCount().

Referenced by DependencyOrderingService\calculateOrder().

getIncomingEdgeCount ( array  $dependencyGraph,   $identifier  )

protected

Get the number of incoming edges in the dependency graph for given identifier

Parameters

array	$dependencyGraph
string	$identifier

Returns

int

Definition at line 198 of file DependencyOrderingService.php.

Referenced by DependencyOrderingService\calculateOrder(), and DependencyOrderingService\findRootIds().

orderByDependencies	(	array	$items,
			$beforeKey = 'before',
			$afterKey = 'after'
	)

Order items by specified dependencies before/after

The dependencies of an items are specified as: 'someItemKey' => [ 'before' => ['someItemKeyA', 'someItemKeyB'] 'after' => ['someItemKeyC'] ]

If your items use different keys for specifying the relations, you can define the appropriate keys by setting the $beforeKey and $afterKey parameters accordingly.

Parameters

array	$items
string	$beforeKey	The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
string	$afterKey	The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'

Returns

array

Exceptions

\UnexpectedValueException

Definition at line 50 of file DependencyOrderingService.php.

References DependencyOrderingService\calculateOrder().

prepareDependencies ( array  $dependencies,   $beforeKey = 'before',   $afterKey = 'after'  )

protected

Prepare dependencies

Ensure that all discovered identifiers are added to the dependency list so we can reliably use the identifiers to build the matrix. Additionally fix all invalid or missing before/after arrays

Parameters

array	$dependencies
string	$beforeKey	The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'
string	$afterKey	The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'

Returns

array Prepared dependencies

Definition at line 266 of file DependencyOrderingService.php.