Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
var MAX_DEPTH = 3;
var work = []; // reusable stack
var seen = []; // "seen hash"
var run = 0;
var findPath = function (source, target, u2f, visitor) { // u2f = user to friend
source = Graph.userToIndex(source);
target = Graph.userToIndex(target);
var i = 0;
var n = 1;
work[0] = new StackEle(source, 0, -1);
++run;
var max_depth = MAX_DEPTH;
var steps = 0;
seen[source] = run;
while(true) { // iterative BFS
if(i >= n) {
return steps;
}
var w = work[i];
var depth = w.depth;
if(depth > max_depth) {
break;
}
var user = w.user;
var friends = u2f[user];
if(!friends) {
++i;
continue;
}
var nextDepth = depth+1
for(var pi = friends.length-1; pi >= 0; --pi) {
var f = friends[pi];
++steps;
if(f === target) { // we found the goal!
max_depth = depth;
var p = [
work[i],
new StackEle(f, nextDepth, null)
];
path = work[i].pos;
while(path >= 0) { // backtrack on the stack
p.unshift(work[path])
path = work[path].pos
}
visitor(source, target, p);
} else {
if(nextDepth <= max_depth && seen[f] !== run) {
seen[f] = run; // mark seen hash with current run
var cur = work[n];
if(cur) { // reuse stack frames to avoid allocations
cur.user = f;
cur.depth = nextDepth;
cur.pos = i;
} else {
work[n] = new StackEle(f, nextDepth, i)
}
++n;
}
}
}
++i
}
return steps
}
function StackEle(user, depth, position) {
this.user = user;
this.depth = depth;
this.pos = position
}
findPath;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.