Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

Basic Dijkstra's Algorithm (assume same edge weights) https://www.youtube.com/watch?v=gdmfOwyQlcI

View JS Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121
// 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)
View JS Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
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
View JS Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
// 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.