topological sort algorithm (v5)

Revision 5 of this benchmark created on

Setup

const c = (() => {
// No. of vertices
let V;
 
// An Array of List which contains
    // references to the Adjacency List of
    // each vertex
let adj;
 
function Graph(v)
{
    V = v;
    adj = new Array(V);
    for (let i = 0; i < V; ++i)
            adj[i] = [];
}
 
// Function to add an edge to graph
function addEdge(u, v)
{
    adj[u].push(v);
}
 
// 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;
             
        // Traverse adjacency lists
        // to fill indegrees of
        // vertices. This step takes
        // O(V+E) time
        for (let i = 0; i < V; ++i) {
            let temp
                = adj[i];
            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,
                // add it to queue
                if (--indegree[adj[u][node]] == 0)
                    q.push(adj[u][node]);
            }
            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);
addEdge(1, 0);
addEdge(2, 0);
addEdge(4, 3);
addEdge(5, 3);
addEdge(6, 3);
addEdge(8, 7);
addEdge(9, 7);

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;
    }
    addTickFunction(tickFunction) {
        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) {
            TickFunctionManager.getInstance().addTickFunction(this);
        }
    }
    /**
     * Adds a tick function dependency if both, the target and the parameter have
     * `canTick` set to `true`.
     *
     * @param tickFunction
     */
    addDependency(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();
        }
        //todo: Trigger event "FunctionTaskCompletion"
        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();
tfc11.addDependency(tfa1);
const c12 = { name: 'c12' };
const tfc12 = new TickFunction(c12);
tfc12.register();
tfc12.addDependency(tfa1);
tfc12.addDependency(tfc11);
const a2 = { name: 'a2' };
const tfa2 = new TickFunction(a2);
tfa2.register();
const c23 = { name: 'c23' };
const tfc23 = new TickFunction(c23);
tfc23.register();
tfc23.addDependency(tfa2);
const c24 = { name: 'c24' };
const tfc24 = new TickFunction(c24);
tfc24.register();
tfc24.addDependency(tfa2);
const c25 = { name: 'c25' };
const tfc25 = new TickFunction(c25);
tfc25.register();
tfc25.addDependency(tfa2);

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;
    }
    addTickFunction(tickFunction) {
        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) {
            TickFunctionManager.getInstance().addTickFunction(this);
        }
    }
    /**
     * Adds a tick function dependency if both, the target and the parameter have
     * `canTick` set to `true`.
     *
     * @param tickFunction
     */
    addDependency(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();
        }
        //todo: Trigger event "FunctionTaskCompletion"
        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();
tfc11.addDependency(tfa1);
const c12 = { name: 'c12' };
const tfc12 = new TickFunction(c12);
tfc12.register();
tfc12.addDependency(tfa1);
tfc12.addDependency(tfc11);
const a2 = { name: 'a2' };
const tfa2 = new TickFunction(a2);
tfa2.register();
const c23 = { name: 'c23' };
const tfc23 = new TickFunction(c23);
tfc23.register();
tfc23.addDependency(tfa2);
const c24 = { name: 'c24' };
const tfc24 = new TickFunction(c24);
tfc24.register();
tfc24.addDependency(tfa2);
const c25 = { name: 'c25' };
const tfc25 = new TickFunction(c25);
tfc25.register();
tfc25.addDependency(tfa2);

return tickFunctionManager
})()

Test runner

Ready to run.

Testing in
TestOps/sec
a
c.topologicalSort()
ready
b
d.startTick()
ready
b (1D array)
old.startTick()
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.