Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
var MAX_DEPTH = 3;
var findPath = function (source, target, u2f, visitor) { // u2f = user to friend
source = Graph.userToIndex(source);
target = Graph.userToIndex(target);
var dist = []
var prev = []
var queue = []
var seen = []
dist[source] = 0
prev[source] = source
queue[queue.length] = source
var len = 1;
while (len > 0) {
var cur = queue.shift() // pop the front element
--len;
var d = dist[cur]
if (cur == target) {
var path = []
var pos = target
while (prev[pos] != source) {
path.unshift({
user: pos
});
pos = prev[pos]
}
visitor(source, target, path)
continue;
//return d
}
if (d > MAX_DEPTH)
return d
var friends = u2f[cur];
if(!friends) continue;
for (var fi = friends.length; fi--; ) {
var next = friends[fi];
if(seen[next]) continue;
seen[next] = true;
var nextd = dist[next] ? dist[next] : 987654321 // inf
if (d + 1 < nextd) {
dist[next] = d + 1
prev[next] = cur
queue[len] = next
++len;
}
}
}
return dist[target]
}
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.