# topological sort algorithm (v5)

## Setup

``````const c = (() => {
// No. of vertices
let V;

// An Array of List which contains
// references to the Adjacency List of
// each vertex

function Graph(v)
{
V = v;
for (let i = 0; i < V; ++i)
}

// Function to add an edge to graph
{
}

// prints a Topological Sort of the
// complete graph
const result = {}

function topologicalSort()
{

// Create a array to store
// indegrees of all
// vertices. Initialize all
// indegrees as 0.
let indegree = new Array(V)
for(let i = 0; i < V; ++i)
indegree[i] = 0;

// to fill indegrees of
// vertices. This step takes
// O(V+E) time
for (let i = 0; i < V; ++i) {
let temp
for (let node = 0; node < temp.length; ++node) {
indegree[temp[node]]++;
}
}

// Create a queue and enqueue
// all vertices with indegree 0
let q = [];
for (let i = 0; i < V; ++i) {
if (indegree[i] == 0)
q.push(i);
}

// Initialize count of visited vertices
let cnt = 0;
const topOrder = []

while (q.length!=0)
{

// Extract front of queue
// (or perform dequeue)
// and add it to topological order
let u = q.shift();
topOrder.push(u)

// Iterate through all its
// neighbouring nodes
// of dequeued node u and
// decrease their in-degree
// by 1
for (let node = 0; node < adj[u].length; node++)
{

// If in-degree becomes zero,
}
cnt++;
}

// Check if there was a cycle
if (cnt != V) {

return;
}

}

// Driver program to test above functions
// Create a graph given in the above diagram
Graph(10);

return { topologicalSort }
})()

const d = (() => {
var ETickGroup;
(function (ETickGroup) {
ETickGroup[ETickGroup["PrePhysics"] = 0] = "PrePhysics";
ETickGroup[ETickGroup["DuringPhysics"] = 1] = "DuringPhysics";
ETickGroup[ETickGroup["PostPhysics"] = 2] = "PostPhysics";
ETickGroup[ETickGroup["MAX"] = 3] = "MAX";
})(ETickGroup || (ETickGroup = {}));
//todo: Keep track of tick time
class TickFunctionManager {
static getInstance() {
if (!this.instance) {
throw new Error(`No instance of TickFunctionManager available.`);
}
return this.instance;
}
constructor() {
/**
* Contains all tick functions, unsorted, in the order they have been added.
*/
this.tickFunctions = [];
/**
* Stores the tick functions for each tick group, sorted by topologial sorting.
*/
this.tickGroups = [];
if (TickFunctionManager.instance) {
throw new Error(`An instance of TickFunctionManager already exists.`);
}
for (let i = 0; i < ETickGroup.MAX; ++i) {
this.tickGroups.push([]);
}
TickFunctionManager.instance = this;
}
if (!this.tickFunctions.includes(tickFunction)) {
tickFunction.index = this.tickFunctions.push(tickFunction) - 1;
return true;
}
return false;
}
startTick() {
// We do topological sorting using Kahn's algorithm (https://en.wikipedia.org/wiki/Topological_sorting)
for (let i = 0; i < this.tickFunctions.length; ++i) {
const tickFunction = this.tickFunctions[i];
const dependencies = tickFunction.dependencies;
for (let j = 0; j < dependencies.length; ++j) {
const dependency = this.tickFunctions[dependencies[j].index];
if (dependency.tickGroup >= tickFunction.tickGroup) {
dependency.indegree++;
}
}
}
const queue = [];
for (let i = 0; i < this.tickFunctions.length; ++i) {
const tickFunction = this.tickFunctions[i];
if (tickFunction.indegree === 0) {
queue.push(tickFunction);
}
}
let iterations = 0;
while (queue.length > 0) {
const tickFunction = queue.shift();
this.tickGroups[tickFunction.tickGroup].push(tickFunction.run);
for (let i = 0; i < tickFunction.dependencies.length; ++i) {
const dependency = tickFunction.dependencies[i];
const node = this.tickFunctions[dependency.index];
if (node && --node.indegree === 0) {
queue.push(node);
}
}
iterations++;
}
if (iterations !== this.tickFunctions.length) {
throw Error(`Dependency cycle detected.`);
}
}
endTick() {
for (let i = 0; i < ETickGroup.MAX; ++i) {
this.tickGroups[i] = [];
}
}
//todo: Should we push rejected tasks into the next tick?
runTickGroup(group) {
return Promise.all(this.tickGroups[group]);
}
}
class TickFunction {
constructor(target) {
this.target = target;
/**
* A list of tick functions that this tick function depends on.
*
* Important: If one of the dependencies is in an earlier tick group,
* that dependency will be ignored! Make sure a dependency is in the same
* or later tick group.
*/
this.dependencies = [];
this.isRegistered = false;
this.isEnabled = true;
this.canTick = false;
this.canTickWhenPaused = false;
this.tickGroup = ETickGroup.PrePhysics;
/**
* The index of where this tick function is stored.
*/
this.index = 0;
/**
* The number of tick functions that depend on this tick function.
*/
this.indegree = 0;
}
async run() {
return true;
}
register() {
if (!this.isRegistered) {
}
}
/**
* Adds a tick function dependency if both, the target and the parameter have
* `canTick` set to `true`.
*
* @param tickFunction
*/
if (this.canTick && tickFunction.canTick) {
if (!this.dependencies.includes(tickFunction)) {
this.dependencies.push(tickFunction);
}
}
}
removeDependency(tickFunction) {
const idx = this.dependencies.indexOf(tickFunction);
if (idx > -1) {
this.dependencies.splice(idx, 1);
}
}
}
//todo: Silently reject when the tick is about to end or the function is taking too long
class TickGroupFunction {
constructor(target) {
this.target = target;
}
async run() {
const result = await this.target.run();
if (result === false) {
return Promise.reject();
}
return true;
}
}
const tickFunctionManager = new TickFunctionManager();
const a1 = { name: 'a1' };
const tfa1 = new TickFunction(a1);
tfa1.register();
const c11 = { name: 'c11' };
const tfc11 = new TickFunction(c11);
tfc11.register();
const c12 = { name: 'c12' };
const tfc12 = new TickFunction(c12);
tfc12.register();
const a2 = { name: 'a2' };
const tfa2 = new TickFunction(a2);
tfa2.register();
const c23 = { name: 'c23' };
const tfc23 = new TickFunction(c23);
tfc23.register();
const c24 = { name: 'c24' };
const tfc24 = new TickFunction(c24);
tfc24.register();
const c25 = { name: 'c25' };
const tfc25 = new TickFunction(c25);
tfc25.register();

return tickFunctionManager
})()

const old = (() => {
var ETickGroup;
(function (ETickGroup) {
ETickGroup[ETickGroup["PrePhysics"] = 0] = "PrePhysics";
ETickGroup[ETickGroup["DuringPhysics"] = 1] = "DuringPhysics";
ETickGroup[ETickGroup["PostPhysics"] = 2] = "PostPhysics";
ETickGroup[ETickGroup["MAX"] = 3] = "MAX";
})(ETickGroup || (ETickGroup = {}));
//todo: Keep track of tick time
class TickFunctionManager {
static getInstance() {
if (!this.instance) {
throw new Error(`No instance of TickFunctionManager available.`);
}
return this.instance;
}
constructor() {
/**
* Contains all tick functions, unsorted, in the order they have been added.
*/
this.tickFunctions = [];
/**
* Stores the tick functions for each tick group, sorted by topologial sorting.
*/
this.tickGroups = [];
if (TickFunctionManager.instance) {
throw new Error(`An instance of TickFunctionManager already exists.`);
}
for (let i = 0; i < ETickGroup.MAX; ++i) {
this.tickGroups.push([]);
}
TickFunctionManager.instance = this;
}
if (!this.tickFunctions.includes(tickFunction)) {
tickFunction.index = this.tickFunctions.push(tickFunction) - 1;
return true;
}
return false;
}
startTick() {
// We do topological sorting using Kahn's algorithm (https://en.wikipedia.org/wiki/Topological_sorting)
for (let i = 0; i < this.tickFunctions.length; ++i) {
const tickFunction = this.tickFunctions[i];
const dependencies = tickFunction.dependencies;
for (let j = 0; j < dependencies.length; ++j) {
const dependency = this.tickFunctions[dependencies[j].index];
if (dependency.tickGroup >= tickFunction.tickGroup) {
dependency.indegree++;
}
}
}
const queue = [];

for (let i = 0; i < this.tickFunctions.length; ++i) {
const tickFunction = this.tickFunctions[i];
if (tickFunction.indegree === 0) {
queue.push(tickFunction);
}
}
let iterations = 0;
const topOrder = []
while (queue.length > 0) {
const tickFunction = queue.shift();
topOrder.push(tickFunction)
for (let i = 0; i < tickFunction.dependencies.length; ++i) {
const dependency = tickFunction.dependencies[i];
const node = this.tickFunctions[dependency.index];
if (node && --node.indegree === 0) {
queue.push(node);
}
}
iterations++;
}
if (iterations !== this.tickFunctions.length) {
throw Error(`Dependency cycle detected.`);
}
}
endTick() {
for (let i = 0; i < ETickGroup.MAX; ++i) {
this.tickGroups[i] = [];
}
}
//todo: Should we push rejected tasks into the next tick?
runTickGroup(group) {
return Promise.all(this.tickGroups[group]);
}
}
class TickFunction {
constructor(target) {
this.target = target;
/**
* A list of tick functions that this tick function depends on.
*
* Important: If one of the dependencies is in an earlier tick group,
* that dependency will be ignored! Make sure a dependency is in the same
* or later tick group.
*/
this.dependencies = [];
this.isRegistered = false;
this.isEnabled = true;
this.canTick = false;
this.canTickWhenPaused = false;
this.tickGroup = ETickGroup.PrePhysics;
/**
* The index of where this tick function is stored.
*/
this.index = 0;
/**
* The number of tick functions that depend on this tick function.
*/
this.indegree = 0;
}
async run() {
return true;
}
register() {
if (!this.isRegistered) {
}
}
/**
* Adds a tick function dependency if both, the target and the parameter have
* `canTick` set to `true`.
*
* @param tickFunction
*/
if (this.canTick && tickFunction.canTick) {
if (!this.dependencies.includes(tickFunction)) {
this.dependencies.push(tickFunction);
}
}
}
removeDependency(tickFunction) {
const idx = this.dependencies.indexOf(tickFunction);
if (idx > -1) {
this.dependencies.splice(idx, 1);
}
}
}
//todo: Silently reject when the tick is about to end or the function is taking too long
class TickGroupFunction {
constructor(target) {
this.target = target;
}
async run() {
const result = await this.target.run();
if (result === false) {
return Promise.reject();
}
return true;
}
}
const tickFunctionManager = new TickFunctionManager();
const a1 = { name: 'a1' };
const tfa1 = new TickFunction(a1);
tfa1.register();
const c11 = { name: 'c11' };
const tfc11 = new TickFunction(c11);
tfc11.register();
const c12 = { name: 'c12' };
const tfc12 = new TickFunction(c12);
tfc12.register();
const a2 = { name: 'a2' };
const tfa2 = new TickFunction(a2);
tfa2.register();
const c23 = { name: 'c23' };
const tfc23 = new TickFunction(c23);
tfc23.register();
const c24 = { name: 'c24' };
const tfc24 = new TickFunction(c24);
tfc24.register();
const c25 = { name: 'c25' };
const tfc25 = new TickFunction(c25);
tfc25.register();

return tickFunctionManager
})()
``````

## Test runner

Testing in
TestOps/sec
a
``c.topologicalSort()``
``d.startTick()``
``old.startTick()``