class CommitOrderCalculator (View source)

CommitOrderCalculator implements topological sorting, which is an ordering algorithm for directed graphs (DG) and/or directed acyclic graphs (DAG) by using a depth-first searching (DFS) to traverse the graph built in memory.

This algorithm have a linear running time based on nodes (V) and dependency between the nodes (E), resulting in a computational complexity of O(V + E).

Constants

NOT_VISITED

IN_PROGRESS

VISITED

Methods

boolean
hasNode(string $hash)

Checks for node (vertex) existence in graph.

void
addNode(string $hash, object $node)

Adds a new node (vertex) to the graph, assigning its hash and value.

void
addDependency(string $fromHash, string $toHash, integer $weight)

Adds a new dependency (edge) to the graph using their hashes.

array
sort()

Return a valid order list of all current nodes.

Details

boolean hasNode(string $hash)

Checks for node (vertex) existence in graph.

Parameters

string $hash

Return Value

boolean

void addNode(string $hash, object $node)

Adds a new node (vertex) to the graph, assigning its hash and value.

Parameters

string $hash
object $node

Return Value

void

void addDependency(string $fromHash, string $toHash, integer $weight)

Adds a new dependency (edge) to the graph using their hashes.

Parameters

string $fromHash
string $toHash
integer $weight

Return Value

void

array sort()

Return a valid order list of all current nodes.

The desired topological sorting is the reverse post order of these searches.

{@internal Highly performance-sensitive method.}

Return Value

array