The boring rants of a lazy nerd

Friday, July 29, 2005

Coding - Topological Sort and Depth-First Search

So, I've actually stumbled into some code at work where I need to implement a topological sort for dependencies. And I've read about DFS and stuff, googled a bit and even opened a real comp-sci textbook we have at the office. While all I really needed was Wikipedia! And I'm prototyping in JavaScript like some microsoftie instead of in Python like real l33t h4x0rz! Oh, the shame!

Anyway, this is what I've come up so far:

Array.prototype.shuffle = function(p_nTimes) {
    if (isNaN(p_nTimes) || (p_nTimes <= 0) || (this.length < 2)) return;
    while (p_nTimes--) {
        var i = Math.floor(Math.random() * this.length);
        var j = Math.floor(Math.random() * this.length);
        var t = this[i];
        this[i] = this[j];
        this[j] = t;
    }
};

function item(p_strName, p_arrDeps) {
    this.Name = p_strName;
    this.arrDeps = p_arrDeps;
    this.bIsInStack = false;
    this.bHasBeenVisited = false;
};

function create_deps(p, k) {
    var deps = {};
    for (var i = 0; i < p; i++) {
        var curr = new item(i, []);
        for (var j = 0; j < i; j++)
            if (Math.floor(Math.random() * 100) % k == 0)
                curr.arrDeps.push(j);
        curr.arrDeps.shuffle(p);
        deps[curr.Name] = curr;
    }
    return deps;
};

function print_deps(deps) {
    for (var i in deps) {
        document.write(deps[i].Name + ': ');
        for (var j = 0; j < deps[i].arrDeps.length; j++)
            document.write(deps[i].arrDeps[j] + ', ');
        document.write('<br/>\n');
    }
    document.write('<br/>\n');
};

function topo_sort_dfs_short_circuit_on_cycle(o) {
    var list = [];
    var cycle = null;

    for (var i in o) {
        (function(p) {
            if (p.bIsInStack) cycle = p.Name;
            if (cycle != null) return;
            p.bIsInStack = true;
            if (!p.bHasBeenVisited) {
                p.bHasBeenVisited = true;
                for (var idxDep = 0; idxDep < p.arrDeps.length; idxDep++)
                    arguments.callee(o[p.arrDeps[idxDep]]);
                list.push(p.Name);
            }
            p.bIsInStack = false;
        })(o[i]);
        if (cycle != null) break;
    }

    return [cycle, list];
};

Next step is trying to see whether a non-recursive implementation is faster (yes, I benchmark JavaScript) and then STL. C# I'll do on company time (haven't installed mono yet).

No comments:

Blog Archive

About Me

GCS d- s-: a-- C++$ UL++ P+++ L+++ E--- W+++ N o? K? w++$ !O !M !V PS-(+) PE Y+ PGP+(-) t--@ 5++(+++) !X R-- tv-- b+>++ DI+++ D+ G e h! r* y--(-)>+++