topological sort algorithm (v2)

Revision 2 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 = {}));
var EInternalTickGroup;
(function (EInternalTickGroup) {
})(EInternalTickGroup || (EInternalTickGroup = {}));
class TickFunctionManager {
    static getInstance() {
        if (!this.instance) {
            throw new Error(`No instance of TickFunctionManager available.`);
        }
        return this.instance;
    }
    constructor() {
        this.tickFunctions = [];
        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.order = this.tickFunctions.push(tickFunction) - 1;
            this.tickGroups[tickFunction.tickGroup].push(tickFunction);
            return true;
        }
        return false;
    }
    startTick() {
        for (let i = 0; i < ETickGroup.MAX; ++i) {
            const tickFunctions = this.tickGroups[i];
            for (let i = 0; i < tickFunctions.length; ++i) {
                const tickFunction = tickFunctions[i];
                const dependencies = tickFunction.dependencies;
                for (let j = 0; j < dependencies.length; ++j) {
                    const dependency = this.tickFunctions[dependencies[j].order];
                    if (dependency) {
                        dependency.indegree++;
                    }
                }
            }
            const queue = [];
            for (let i = 0; i < tickFunctions.length; ++i) {
                const tickFunction = tickFunctions[i];
                if (tickFunction.indegree === 0) {
                    queue.push(tickFunction);
                }
            }
            let visitCount = 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.order];
                    if (node && --node.indegree === 0) {
                        queue.push(node);
                    }
                }
                visitCount++;
            }
            if (visitCount !== tickFunctions.length) {
                throw Error(`Dependency cycle detected.`);
            }
        }
    }
    endTick() { }
    runTickGroup(group) { }
}
class TickFunction {
    constructor(target) {
        this.target = target;
        this.dependencies = [];
        this.isRegistered = false;
        this.isEnabled = true;
        this.canTick = true;
        this.canTickWhenPaused = false;
        this.tickGroup = ETickGroup.PrePhysics;
        this.order = -1;
        this.indegree = 0;
        this.name = '';
    }
    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);
        }
    }
}
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 = {}));
var EInternalTickGroup;
(function (EInternalTickGroup) {
})(EInternalTickGroup || (EInternalTickGroup = {}));
class TickFunctionManager {
    static getInstance() {
        if (!this.instance) {
            throw new Error(`No instance of TickFunctionManager available.`);
        }
        return this.instance;
    }
    constructor() {
        this.tickFunctions = [];
        if (TickFunctionManager.instance) {
            throw new Error(`An instance of TickFunctionManager already exists.`);
        }
        TickFunctionManager.instance = this;
    }
    addTickFunction(tickFunction) {
        const idx = this.tickFunctions.indexOf(tickFunction);
        if (idx > -1) {
            return false;
        }
        tickFunction.order = this.tickFunctions.push(tickFunction) - 1;
        return true;
    }
    // Tick groups are the final hierarchy. If a tick function has a dependency that is being resolved
    // in a later tick group, that dependency will be ignored for that tick function.
    startTick() {
        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 tickFunction = this.tickFunctions[dependencies[j].order];
                if (TickFunction) {
                    tickFunction.indegree++;
                }
            }
        }
        const queue = [];
        const topOrder = []
        for (let i = 0; i < this.tickFunctions.length; ++i) {
            const tickFunction = this.tickFunctions[i];
            topOrder.push(tickFunction)
            if (tickFunction.indegree === 0) {
                queue.push(tickFunction);
            }
        }
        let visitCount = 0;
        while (queue.length > 0) {
            const tickFunction = queue.shift();
            for (let i = 0; i < tickFunction.dependencies.length; ++i) {
                const dependency = tickFunction.dependencies[i];
                const node = this.tickFunctions[dependency.order];
                if (node && --node.indegree === 0) {
                    queue.push(node);
                }
            }
            visitCount++;
        }
        if (visitCount !== this.tickFunctions.length) {
            throw Error(`Dependency cycle detected.`);
        }
    }
    endTick() {
    }
    runTickGroup(group) { }
}
class TickFunction {
    constructor(target) {
        this.target = target;
        this.dependencies = [];
        this.isRegistered = false;
        this.isEnabled = true;
        this.canTick = true;
        this.canTickWhenPaused = false;
        this.tickGroup = ETickGroup.PrePhysics;
        this.order = -1;
        this.indegree = 0;
        this.name = '';
    }
    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);
        }
    }
}
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.