Skip to content

@EpiphanyMachine /JS Solution
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Basic Dijkstra's Algorithm (assume same edge weights) https://www.youtube.com/watch?v=gdmfOwyQlcI
// thanks to:
// Adam - https://github.com/acreeger
// Juan - https://github.com/nilnullzip
// Note that I decided the search order heuristic should be based solely on the person being visited
// and the goal person. The position within the graph should not be considered, so the graph edges
// are not annotated. Rather a heuristic function is used that takes as input only two people. I believe
// this makes more sense if the heuristic is based on things like number of friends or similarity in
// things like: school, city, job, etc.
// class for graph
function Person (name, friends) {
Person.id =3D Person.id || 0;
this.id =3D Person.id++;
this.name =3D name;
this.friends =3D friends || {}; // List of Persons
graph[this.id] =3D this;
}
Person.prototype.make_friends =3D function(f) {
this.friends[f.id] =3D f;
f.friends[this.id] =3D this;
return this;
}
// Huristic function returns relative priority for searching
// Note: independent of graph, only depends on the two persons
function priority (a, b) {
return 1;
}
// Breadth first search
// Algorithm based on visited and frontier nodes
function search(goal, frontier, visited) {
visited =3D visited || {};
frontier.sort(function(a,b){priority(a,b)}); // Search in order =
specified by huristic
var next =3D {};
for (i in frontier) { // Frontier is array
person =3D frontier[i];
if (person.id =3D=3D goal.id) {
return 0; // Found goal!
}
visited[person.id] =3D person;
for (var id in person.friends) { // Friends is hash with =
id as key
if (!visited[id]) {
next[id] =3D person.friends[id];
}
}
}
if (Object.keys(next).length=3D=3D0) {
return Infinity; // No path to goal
} else {
var next_array =3D [];
for (k in next) next_array.push(next[k]);
return search(goal, next_array, visited) + 1; // =
Recurse to next level in search
}
}
// Very simple test
var graph =3D {}; // The entire graph
j =3D new Person("Juan");
a =3D new Person("Adam");
g =3D new Person("Greg");
j.make_friends(a);
g.make_friends(a);
var start =3D j;
var goal =3D g;
console.log("Juan and Greg are " + search(goal, [start], {}) + " levels =
apart")
console.log("\n\n-----------------------------\n\n")
// Adam's test data
graph =3D {}
var will =3D new Person("will");
var peter =3D new Person("peter");
var eric =3D new Person("eric");
var christina =3D new Person("christina");
var drew =3D new Person("drew")
var tori =3D new Person("tori")
var tobias =3D new Person("tobias")
var tris =3D new Person("tris")
tobias.make_friends(eric,5).make_friends(tori, 4);
tris.make_friends(tobias,7).make_friends(christina, 5)
christina.make_friends(peter, 4).make_friends(drew, 6)
drew.make_friends(peter, 8)
eric.make_friends(peter,8)
tori.make_friends(eric, 4)
console.log("How close are tris and peter?")
visited =3D {}
var levels =3D search(tris, [peter]);
console.log("They are %s level(s) apart.", levels)
console.log("\n\n-----------------------------\n\n")
console.log("How close are tris and drew?")
visited =3D {}
var levels =3D search(tris, [drew]);
console.log("They are %s level(s) apart.", levels)
console.log("\n\n-----------------------------\n\n")
console.log("How close are tori and christina?")
visited =3D {}
var levels =3D search(tori, [christina]);
console.log("They are %s level(s) apart.", levels)
console.log("\n\n-----------------------------\n\n")
console.log("How close are tris and will?")
visited =3D {}
var levels =3D search(tris, [will]);
console.log("They are %s level(s) apart.", levels)
LinkedIn Connections. aka: degrees of separations.
Assume a social network.
Two people are signed up for your site, and you want to know how many people
are between them?
function getNumberOfNodesBetween(graph, node1, node2){
return number;
}
getFriend(node) => array of all of a user's friends.
What is the time complexity?
What is the memory complexity?
BASIC:
Assume each connection has the same relative probability.
ADVANCED:
Assume each connection is assigned a relative probability of finding the other person?
Wiki: Weighted Graph
// Thanks to
// Kris
Assume a social network.
Two people signed for your site, how many first connections between them?
var graph = [ {node1:a, node2:c} ,{node1:c, node2:b}, {node1:c,node2:d}, {node1:d,node2:e}, {node1:c, node2:e} ] ;
var A = {
id : nameA,
distance_array : [ {node:'c',distance:1}]
distance_array : [ {node:'c',distance:1}, {node:'b',distance:2},
distance_array : [ {node:'c',distance:1}, {node:'b',distance:2}, {node:d, distance:2}, {node:e, distance:2} ]
},
var B = {
id : nameb,
distance_array : [ {c,1}, {} ]
}
function getNumberOfNodesBetween(graph, node1, node2) {
var array1 = node1.distance_array;
array1.forEach(function(obj){
if (obj.node == node2) {
return obj.distance;
}
});
}
getFriend(node) => array of all of a user's friends
getNumberOfNodesBetweeen(graph, A, B)
=== partial actual code==
var Node = function (name ) {
this.id = name;
this.distance_array = [];
}
var graph = [ {node1:a, node2:c} , {node1:e, node2:b} ,{node1:c, node2:b}, {node1:c,node2:d}, {node1:d,node2:e}, {node1:c, node2:e} ] ;
var a = new Node("a");
var allNodes = [];
console.log("a =" + JSON.stringify(a));
var i =0;
for ( i = 0; i < graph.length; i++ ) {
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.