DependencyOrderingService

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

Table of Contents

Methods

buildDependencyGraph()  : array<string|int, array<string|int, bool>>
Builds the dependency graph for the given dependencies
calculateOrder()  : array<string|int, mixed>
Calculate an ordered list for a dependencyGraph
findRootIds()  : array<string|int, mixed>
Find all root nodes of a graph
orderByDependencies()  : array<string|int, mixed>
Order items by specified dependencies before/after
findPathInGraph()  : array<string|int, mixed>
Find any path in the graph from given start node to destination node
getIncomingEdgeCount()  : int
Get the number of incoming edges in the dependency graph for given identifier
prepareDependencies()  : array<string|int, mixed>
Prepare dependencies

Methods

buildDependencyGraph()

Builds the dependency graph for the given dependencies

public buildDependencyGraph(array<string|int, mixed> $dependencies[, string $beforeKey = 'before' ][, string $afterKey = 'after' ]) : array<string|int, array<string|int, bool>>

The dependencies have to specified in the following structure:

$dependencies = [
  'someKey' => [
     'before' => ['someKeyA', 'someKeyB']
     'after' => ['someKeyC']
  ]
]

We interpret a dependency like

  'A' => [
    'before' => ['B'],
    'after' => ['C', 'D']
  ]

as

  • A depends on C
  • A depends on D
  • B depends on A
Parameters
$dependencies : array<string|int, mixed>
$beforeKey : string = 'before'

The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'

$afterKey : string = 'after'

The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'

Return values
array<string|int, array<string|int, bool>> —

The dependency graph

calculateOrder()

Calculate an ordered list for a dependencyGraph

public calculateOrder(array<string|int, array<string|int, bool>> $dependencyGraph) : array<string|int, mixed>
Parameters
$dependencyGraph : array<string|int, array<string|int, bool>>
Tags
throws
UnexpectedValueException
Return values
array<string|int, mixed> —

Sorted array of keys of $dependencies

findRootIds()

Find all root nodes of a graph

public findRootIds(array<string|int, array<string|int, bool>> $dependencyGraph) : array<string|int, mixed>

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
$dependencyGraph : array<string|int, array<string|int, bool>>
Return values
array<string|int, mixed> —

List of identifiers which are root nodes

orderByDependencies()

Order items by specified dependencies before/after

public orderByDependencies(array<string|int, mixed> $items[, string $beforeKey = 'before' ][, string $afterKey = 'after' ]) : array<string|int, mixed>

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
$items : array<string|int, mixed>
$beforeKey : string = 'before'

The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'

$afterKey : string = 'after'

The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'

Tags
throws
UnexpectedValueException
Return values
array<string|int, mixed>

findPathInGraph()

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

protected findPathInGraph(array<string|int, mixed> $graph, string $from, string $to) : array<string|int, mixed>
Parameters
$graph : array<string|int, mixed>

Directed graph

$from : string

Start node

$to : string

Destination node

Return values
array<string|int, mixed> —

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

getIncomingEdgeCount()

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

protected getIncomingEdgeCount(array<string|int, mixed> $dependencyGraph, string $identifier) : int
Parameters
$dependencyGraph : array<string|int, mixed>
$identifier : string
Return values
int

prepareDependencies()

Prepare dependencies

protected prepareDependencies(array<string|int, mixed> $dependencies[, string $beforeKey = 'before' ][, string $afterKey = 'after' ]) : array<string|int, mixed>

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
$dependencies : array<string|int, mixed>
$beforeKey : string = 'before'

The key to use in a dependency which specifies the "before"-relation. eg. 'sortBefore', 'loadBefore'

$afterKey : string = 'after'

The key to use in a dependency which specifies the "after"-relation. eg. 'sortAfter', 'loadAfter'

Return values
array<string|int, mixed> —

Prepared dependencies


        

        
    




    

    

                            

            

                            
    

        On this page

        
    


            

                    

        

    

        

            
Search results