Version: 4.3

Class: CommitOrderCalculator

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).

Based on https://github.com/doctrine/orm/blob/master/lib/Doctrine/ORM/Internal/CommitOrderCalculator.php

Hierarchy

  • CommitOrderCalculator

Properties

nodes

Private nodes: Dictionary<Node>

Defined in packages/core/src/unit-of-work/CommitOrderCalculator.ts:34

Matrix of nodes, keys are provided hashes and values are the node definition objects.


sortedNodeList

Private sortedNodeList: string[] = []

Defined in packages/core/src/unit-of-work/CommitOrderCalculator.ts:37

Volatile variable holding calculated nodes during sorting process.

Methods

addDependency

addDependency(from: string, to: string, weight: number): void

Defined in packages/core/src/unit-of-work/CommitOrderCalculator.ts:56

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

Parameters:

NameType
fromstring
tostring
weightnumber

Returns: void


addNode

addNode(hash: string): void

Defined in packages/core/src/unit-of-work/CommitOrderCalculator.ts:49

Adds a new node to the graph, assigning its hash.

Parameters:

NameType
hashstring

Returns: void


discoverProperty

discoverProperty(prop: EntityProperty, entityName: string): void

Defined in packages/core/src/unit-of-work/CommitOrderCalculator.ts:60

Parameters:

NameType
propEntityProperty
entityNamestring

Returns: void


hasNode

hasNode(hash: string): boolean

Defined in packages/core/src/unit-of-work/CommitOrderCalculator.ts:42

Checks for node existence in graph.

Parameters:

NameType
hashstring

Returns: boolean


sort

sort(): string[]

Defined in packages/core/src/unit-of-work/CommitOrderCalculator.ts:81

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.

Returns: string[]


visit

Privatevisit(node: Node): void

Defined in packages/core/src/unit-of-work/CommitOrderCalculator.ts:102

Visit a given node definition for reordering.

internal Highly performance-sensitive method.

Parameters:

NameType
nodeNode

Returns: void


visitOpenNode

PrivatevisitOpenNode(node: Node, target: Node, edge: Edge): void

Defined in packages/core/src/unit-of-work/CommitOrderCalculator.ts:124

Visits all target's dependencies if in cycle with given node

Parameters:

NameType
nodeNode
targetNode
edgeEdge

Returns: void

Last updated on by Martin Adámek