Instantly share code, notes, and snippets.

# EpiphanyMachine/JS Solution Created Dec 4, 2013

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++ ) { }