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

bool
hasNode(string $hash)

Checks for node (vertex) existence in graph.

addNode(string $hash, object $node)

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

addDependency(string $fromHash, string $toHash, int $weight)

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

object[]
sort()

Return a valid order list of all current nodes.

Details

bool hasNode(string $hash)

Checks for node (vertex) existence in graph.

Parameters

string $hash

Return Value

bool

addNode(string $hash, object $node)

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

Parameters

string $hash
object $node

addDependency(string $fromHash, string $toHash, int $weight)

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

Parameters

string $fromHash
string $toHash
int $weight

object[] 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

object[]