CommitOrderCalculator
in package
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).
Table of Contents
- IN_PROGRESS = 1
- NOT_VISITED = 0
- VISITED = 2
- $nodeList : array<string|int, stdClass>
- Matrix of nodes (aka. vertex).
- $sortedNodeList : mixed
- Volatile variable holding calculated nodes during sorting process.
- addDependency() : void
- Adds a new dependency (edge) to the graph using their hashes.
- addNode() : void
- Adds a new node (vertex) to the graph, assigning its hash and value.
- hasNode() : bool
- Checks for node (vertex) existence in graph.
- sort() : mixed
- Return a valid order list of all current nodes.
- visit() : void
- Visit a given node definition for reordering.
Constants
IN_PROGRESS
public
mixed
IN_PROGRESS
= 1
NOT_VISITED
public
mixed
NOT_VISITED
= 0
VISITED
public
mixed
VISITED
= 2
Properties
$nodeList
Matrix of nodes (aka. vertex).
private
array<string|int, stdClass>
$nodeList
= []
Keys are provided hashes and values are the node definition objects.
The node state definition contains the following properties:
-
state (integer) Whether the node is NOT_VISITED or IN_PROGRESS
-
value (object) Actual node value
-
dependencyList (array
) Map of node dependencies defined as hashes.
$sortedNodeList
Volatile variable holding calculated nodes during sorting process.
private
mixed
$sortedNodeList
= []
Tags
Methods
addDependency()
Adds a new dependency (edge) to the graph using their hashes.
public
addDependency(string $fromHash, string $toHash, int $weight) : void
Parameters
- $fromHash : string
- $toHash : string
- $weight : int
Return values
void —addNode()
Adds a new node (vertex) to the graph, assigning its hash and value.
public
addNode(string $hash, object $node) : void
Parameters
- $hash : string
- $node : object
Return values
void —hasNode()
Checks for node (vertex) existence in graph.
public
hasNode(string $hash) : bool
Parameters
- $hash : string
Return values
bool —sort()
Return a valid order list of all current nodes.
public
sort() : mixed
The desired topological sorting is the reverse post order of these searches.
Tags
Return values
mixed —visit()
Visit a given node definition for reordering.
private
visit(stdClass $vertex) : void
Parameters
- $vertex : stdClass