2f:null 30:["$","title",null,{"children":"Algorithmic Game Theory Final Project | lylpasko | Observable"}] 36:T5ba,viewof graph = { const form = html``; const graphs = {1: iterations.graph1, 2: iterations.graph2, 3: iterations.graph3, 4: iterations.graph4}; const timeout = setInterval(() => { form.value = graphs[form.radio.value = (+form.radio.value) % 4 + 1]; form.dispatchEvent(new CustomEvent("input")); }, 2300); form.onchange = () => form.dispatchEvent(new CustomEvent("input")); // Safari form.oninput = event => { if (event.isTrusted) clearInterval(timeout), form.onchange = null; form.value = graphs[form.radio.value]; }; form.value = graphs[form.radio.value]; invalidation.then(() => clearInterval(timeout)); return form; }37:T1344,chart = { const nodes = iterations.graph1.nodes; const links = iterations.graph1.links; const radius = 12; const svg = d3.create("svg") .attr("viewBox", [0, 0, width, height]); const forceSim = d3.forceSimulation(nodes) .force("link", d3.forceLink(links).id(d => d.id).distance(65).strength(0.7)) .force("charge", d3.forceManyBody().strength(20)) .force('collision', d3.forceCollide().radius(35)) .force("center", d3.forceCenter(width / 2, height / 2)); svg.append("svg:defs").selectAll("marker") .data(["arrowhead"]) .enter().append("svg:marker") .attr("id", String) .attr("viewBox", "0 -5 10 10") .attr("refX", 21).attr("refY", 0) .attr("markerWidth", radius*2/3) .attr("markerHeight", radius*2/3) .attr("stroke", "#ccc") .attr("orient", "auto") .append("svg:path") .attr("d", "M0,-5L10,0L0,5"); let link = svg.append("g") .attr("stroke", "#ff8c00") .attr("stroke-opacity", 0.6) .selectAll("line") .data(links) .join("line") .attr("stroke-width", 1.2) .attr("marker-end", "url(#arrowhead)"); // add the arrowhead let node = svg.append("g") .selectAll("circle") .data(nodes) .join("circle") .attr("stroke", outline) .attr("r", radius) .attr("fill", color) // .style("fill-opacity",0.8) .call(drag(forceSim)); const text = svg.append("g") .attr("stroke", "black") .attr("stroke-opacity", 0.6) .selectAll("text") .data(nodes) .join("text") .attr("fill", "#999") .style("font-size", "15") .style("font-weight", "bold") .style("font-family", "serif") .text(d => d.id); let label = svg.append("g") .attr("stroke", "black") .attr("stroke-opacity", 0.6) .selectAll("text") .data(nodes) .join("text") .attr("fill", "#631") .call(drag(forceSim)) .attr("text-anchor", "middle") .style("font-size", "15") .style("font-family", "monospace"); // legend svg.append("circle").attr("cx",width-130).attr("cy",20).attr("r", radius-2) .attr("stroke", "#458B00").attr("stroke-width", 2).style("fill","#fff"); svg.append("circle").attr("cx",width-130).attr("cy",50).attr("r", radius-2) .attr("stroke", "#8B0000").attr("stroke-width", 2).style("fill", "#fff"); svg.append("text").attr("x", width-105).attr("y", 21).text("Allocated").style("font-size", "15px") .style("font-family", "serif").attr("alignment-baseline","middle") svg.append("text").attr("x", width-105).attr("y", 51).text("Unallocated").style("font-size", "15px") .style("font-family", "serif").attr("alignment-baseline","middle") forceSim.on("tick", () => { link .attr("x1", d => d.source.x) .attr("y1", d => d.source.y) .attr("x2", d => d.target.x) .attr("y2", d => d.target.y) .style("stroke", d => { return (d.inCycle) ? "#036440" : "#cc7000" }) // links in a cycle are green .style("stroke-opacity", d => { return (d.inCycle) ? 1 : 0.6 }) node // constrain positions within boundary of the SVG .attr("cx", function(d) { return d.x = Math.max(radius, Math.min(width - radius-20, d.x)); }) .attr("cy", function(d) { return d.y = Math.max(radius, Math.min(height - radius-20, d.y)); }) text .attr("x", d => d.x - 20) .attr("y", d => d.y - 13); label .attr("x", d => d.x - 0.5) .attr("y", d => d.y + 5) .text(d => d.item); }); invalidation.then(() => forceSim.stop()); return Object.assign(svg.node(), { update({nodes, links}) { // Make a shallow copy to protect against mutation, while // recycling old nodes to preserve position and velocity. const old = new Map(node.data().map(d => [d.id, d])); nodes = nodes.map(d => Object.assign(old.get(d.id) || {}, d)); links = links.map(d => Object.assign({}, d)); // update initial svg elements to place visual cues for allocation node = node .data(nodes, d => d.id) .join(enter => enter.append("circle") .attr("r", 8) .attr("fill", d => color(d.id))) .attr("stroke", outline) // highlight green for allocated .attr("stroke-width", d => { return (d.alloc) ? 2 : 1}); link = link // regenerate coordinates and styles .data(links, d => [d.source, d.target]) .join("line") .attr("stroke-width", 1.2) .attr("marker-end", "url(#arrowhead)"); // add the arrowhead forceSim.nodes(nodes); forceSim.force("link").links(links); forceSim.force("charge", function(node) { return (node.alloc) ? 0 : d3.forceManyBody().strength(20); }); forceSim.alpha(1).restart(); } }); }38:T677,md`### Definition (Top Trading Cycles Algorithm) For each player ${tex`i`} of the N players, create an edge ${tex`(i,f(i))`} where ${tex`f(i)`} is the player that is currently assigned to ${tex`i`}'s most highly ranked item. Let ${tex`G`} be the graph constructed from the N player vertices and these edges. **while** ${tex`N\neq\emptyset`} **do** **for each** ${tex`n\in N`} **do** Let ${tex`C_n`} be the set of nodes in the cycles starting from node n **if** ${tex`C_n \neq \emptyset`} **then** **for each** node u in ${tex`C_n`} **do** Let ${tex`\{u, v\}`} be the outgoing edge from u Assign v to u Remove edge ${tex`\{u, v\}`} **else if** ${tex`C_n = \emptyset`} **then** continue remove ${tex`C_n`} from the graph G Let R be the set of remaining nodes in the graph. **for each** r in R **do** create an edge ${tex`(r,f(r))`}; **set** ${tex`N = R`}. `39:Ta78,md` ## Optimality of TTC The allocation returned by the Top Trading Cycle algorithm has several important properties. An important note to realize is that the TTC allocation always improves (or does not make worse) on the initial allocation to the players. First, it is important to understand that this mechanism will always terminate because at each iteration, there is always at least one directed cycle. This stems from each vertex having an outdegree of 1, which is similar to an acyclic tree, but with one extra edge to force a cycle. With a guaranteed allocation, it is easy to see that each player won't get any house less preferred than their own, because whenever they want their own house, a self-loop in the TTC provides it. ### Theorem 1. _TTC is Incentive Compatible_. Another important property of TTC (and any matching algorithm) is _incentive compatibility_, which ensures that it is in everyone's best interest to be honest. Without this, one person can gain a higher allocation by lying about preferences. The basis of incentive compatibility is that in the iteration that a player is assigned a house, it was their favorite house available. The reason they couldn't get any of their more preferable houses was they either were already assigned, or were already part of a cycle in that iteration. So why couldn't a player, knowing they can't get their first choice, list a different choice as their top? This happens because a cycle must be formed to obtain a house. This cycle includes a path to said player, which means all players in this path will get a house at the same time as the player. That means that the player can't get a house in an earlier iteration, so they can only rely on the best house available at the iteration they're destined for. ${tex`\square`} To denote the quality of the resulting allocation, we can check if any member of the group can individually benefit without the expense of another. Since it's impossible for only one person to change houses, this is equivalent to checking if a group can reallocate houses such that every member of the group is better off. Such a group is known as a _blocking coalition_, and an allocation without blocking coalitions is called a _core allocation_. ### Theorem 2. _TTC returns a core allocation_. Clearly, blocking coalitions are impossible in the TTC allocation. Any reallocation among a blocking coalition involves cycle of higher-ranked houses. This cycle would've appeared in the TTC mechanism and already been allocated. Thus, we can see that TTC provides an allocation that forces players to be honest and provides the best allocation to meet everyone's demands. ${tex`\square`}` 3a:Ta0d,md`### Extension to existing tenants with ranks. In practical situations, the set of items is not always bijective with the players. A natural extension of the allocation problem therefore considers allocation of items to new (unallocated) and existing (pre-allocated) tenants. This involves a set of occupied homes and a set of unoccupied homes, and a set each for existing tenants and incoming tenants. The current matching of existing tenants to occupied homes is known. Moreover, the mechanism is provided with a ranking of all tenants. This ranking could be determined by seniority, time of application, or any other option that provides a complete ordering of the tenants. Unfortunately, it is clear that TTC cannot be used as there no longer exists a one-to-one relation between players and houses. Atila Abdulkadiroglu and Tayfun Sonmez introduce an extension of the TTC that uses the same premise of cycle detection, but accounts for the difference between houses and players. This mechanism uses a vertex for each house and one for each player. In each iteration, directed edges are created from each player to their favorite house in the graph, just like the general case. However, for occupied houses, an edge is drawn to its current tenant if available. If not, and for unoccupied houses, an edge is drawn to the highest priority tenant that does not already have an incoming edge. Then, cycles once again determine assignments, and those are removed from the graph before a new iteration begins. Being determined by cycles, this mechanism maintains the same important properties as TTC. Every existing tenant is at least better off because they can always just create a cycle with their current home. The argument for incentive compatibility remains the same, as obtaining a house requires a path of nodes pointing to you, which predetermines which iteration you will obtain a house. Since you always "point" to the best house available, you will obtain the best house in your iteration. The core allocation, or making sure no party can cooperatively improve, is also maintained because any reallocation depends on cycles or players pointing to higher preferences, which would have already been considered. This algorithm also honors player priority, since if there are too many applying tenants, the ones at the back of the line will never have an edge pointed to them unless the players in front get assigned. This makes the mechanism very similar to allocating all empty houses among the highest priority unassigned tenants, and then using TTC. ` 3b:T4f0,/* Reallocation step of TTC. For each directed cycle in the graph, set the appropriate allocation and create a new graph among unallocated nodes according to their highest remaining priority. @params flatlinks An "engineering variable" which specifies whether graphData a shortened links array (with only node ids) or a long array (with node objects). */ reallocate = (graphData, flatlinks = true) => { const oldNodes = JSON.parse(JSON.stringify(graphData.nodes)); const oldLinks = JSON.parse(JSON.stringify(graphData.links)); const allCycles = detectCycles(oldNodes, oldLinks, flatlinks); //mutates alloc and item field of oldNodes let allocNodes = []; let freeNodes = []; oldNodes.forEach( function(n) { if (n.alloc) { // for previously and newly allocated nodes n.x = 20; n.y = ((n.id+1) / nodes.length) * height; allocNodes.push(n); } else { // unallocated nodes n.y = ((n.id+1)/nodes.length)*height; freeNodes.push(n) } }); let links = generateLinks(freeNodes, flatlinks); allCycles.forEach( function(n) { // newly allocated nodes }); const updated = { allocNodes, freeNodes, links }; return updated; } 3c:T578,findCycle = (start, links, flatlinks = true) => { let currId = start.id; let cycle = []; let found = false; let iterations = 0; let maxIter = links.length; while (!found && iterations < maxIter) { // find the outedge of the current source node (each node has outdegree 1) if (flatlinks) { links.forEach( function(li) { if (li.inCycle) { return; } if (li.source == currId) { const node = li.source; const item = li.target; if (item == start.id) { found = true; } const allocated = {node, item, li}; cycle.push(allocated); currId = item; return; }; }); } else { // for post-d3.forceSimulation(nodes).forceLink() execution links.forEach( function(li) { if (li.inCycle) { return; } if (li.source.id == currId) { const node = li.source; const item = li.target.id; if (item == start.id) { found = true; } const allocated = {node, item, li}; // the ID of each node is its house cycle.push(allocated); currId = item; return; // stops forEach }; }); }; iterations = iterations + 1; if (found) { cycle.forEach( function(c) { c.li.inCycle = true; }); return cycle; }; }; return null; };3d:[{"id":"768c98f46fc290e3a1d0311a4506656d244830db255cd7a235ab9deeccff2de1e9a6442168e38f2a656527948523de668a6e014433f04c6d582633ebe07ac716","href":"https://static.observableusercontent.com/files/768c98f46fc290e3a1d0311a4506656d244830db255cd7a235ab9deeccff2de1e9a6442168e38f2a656527948523de668a6e014433f04c6d582633ebe07ac716","name":"desires@9.json","type":"application/json","lastModified":1588874054408.071,"size":1385}] 33:{"id":"8c30f271161d2d03","slug":"algorithmic-game-theory-final-project","title":"Algorithmic Game Theory Final Project","thumbnail":"09d2526f45e04c1872c5f6ef0e00d23cd8c6f03421fba1c5c4f0a50a25f51036","access_level":"public","create_time":"$D2020-05-05T19:49:17.166Z","update_time":"$D2020-05-31T02:52:49.662Z","view_time":null,"first_public_time":"$D2020-05-31T04:11:13.911Z","has_unpublished_edits":null,"fork":{"id":"a6c00de7c09bdfa1","slug":"force-directed-graph-component","title":"Force-directed graph component","owner":{"id":"863951e3ebe4c0ae","login":"d3","name":"D3"}},"stars":10,"starred":false,"owner":{"type":"team","id":"a758fc4a07ec56d6","login":"lylpask","name":"lylpasko","avatar_url":"https://avatars-next.observableusercontent.com/6e00fe2784d2cc5d1a8c6ee18dd79be41d5eadef984a54e39a79e019407fd6d6","tier":"starter_2024"},"version":1525,"publish_version":1525,"role":null,"authored":false,"authors":[{"type":"individual","id":"05e685795178744b","login":"lylpask","name":"lylpasko","avatar_url":"https://avatars-next.observableusercontent.com/6e00fe2784d2cc5d1a8c6ee18dd79be41d5eadef984a54e39a79e019407fd6d6","tier":null}],"members":[{"type":"individual","id":"05e685795178744b","login":"lylpask","name":"lylpasko","avatar_url":"https://avatars-next.observableusercontent.com/6e00fe2784d2cc5d1a8c6ee18dd79be41d5eadef984a54e39a79e019407fd6d6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":6,"collection":null,"type":"notebook","body":{"title":"Algorithmic Game Theory Final Project","cells":[{"id":1,"value":"md`# Algorithmic Game Theory Final Project`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"md`We present a [visualization](#visualization) of the Top Trading Cycles (TTC) algorithm for the classic housing allocation game. \nThe greedy TTC algorithm is illustrated step-by-step with a dynamic network graph.\n\nWe also generalize the problem to a more realistic context and discuss a extension of the allocation game with pre-allocated items. A mechanism is provided for the generalized problem, and shown to be optimal as a core allocation and incentive-compatible partial matching.\n\nWritten by Lyle Paskowitz, Stephanie Zhang, Tanuj Alapati, and Kaushik Srinivasan as a final project for Algorithmic Game Theory (EN.601.436/636), taught at Johns Hopkins in Spring 2020 by Professor Mike Dinitz. `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1383,"value":"md`### Definition (House Allocation problem)\nConsider a set ${tex`N`} of ${tex`n`} players. Each player ${tex`i\\in N`} has an ordering, or ranking, over a set of ${tex`n`} houses. Is there an allocation (bijection) between players or items such that each player gets a highly-ranked house?\n\nThe house allocation problem is generalized by removing the one-to-one assumption and equality, e.g. allowing multiple players to be assigned to the same house or allowing more tenants than houses, with some tenants given priority to others. Such generalizations lead to mechanisms for general matchings such as the National Residency Match Program, and are discussed in the [section below](#Extension to existing tenants with ranks).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":367,"value":"md`\n### Problem Motivation\nConsider a kidney donor exchange, in which there are an equal number of people and kidneys they can receive. Because person A cannot be assigned a kidney from person B without ensuring B also receives a kidney from elsewhere, the current assignments and preferences provide a real example of such a dependency graph. \nAnother example is assigning university housing, in which returning students may wish to change rooms, and incoming (freshman) students need an unoccupied room. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":961,"value":"players = data.nodes","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1378,"value":"md`You can choose a player index and view their preference. In this example, player ${itemHover} prefers house ${data.nodes[itemHover].rank[0]} the most and house ${data.nodes[itemHover].rank[data.nodes[itemHover].rank.length - 1]} the least.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1374,"value":"viewof itemHover = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1399,"value":"ranks = players[itemHover].rank","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1327,"value":"md`## Visualization`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":956,"value":"md`\nBelow is an instance of TTC algorithm on an instance of fourteen players (nodes). Each player is initially allocated their own item (e.g. a house), and has a personal ranking of the entire set of items. As the steps progress, new directed cycles are formed and subsequently allocated (indicated by nodes with a green border). Nodes bordered in red are not yet allocated by the algorithm. \n\nYou can pause the visualization at any step to drag and inspect its nodes.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":487,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1369,"value":"md`There are four steps to the algorithm for this data: the second step allocates two cycles, the third one cycle, and the fourth two cycles, including a self-link. The raw data for the algorithm is listed in the cell below.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":600,"value":"iterations = { // graph1 is initialized below\n // renderGraphX is intermediary step between graphX-1 and graphX+1\n const graph2 = nextGraph(graph1); \n detectCycles(graph2.nodes, graph2.links);\n const graph3 = nextGraph(graph2); \n detectCycles(graph3.nodes, graph3.links);\n const graph4 = nextGraph(graph3);\n detectCycles(graph4.nodes, graph4.links);\n return {graph1, graph2, graph3, graph4}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":369,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":374,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":376,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1039,"value":"md`### Helper functions\nEach cell runs as a separate script in topological order, from a dependency DAG. Loosely, the functions below are arranged from highest- to lowest-level, or the most- to least-dependent, or bottom to top of the call stack.\n\nThis is my first try at D3; please forgive all the _O(mn)_ graph searches c:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":793,"value":"chart.update(graph);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":596,"value":"nextGraph = (graphData, flatlinks = true) => {\n let newData = JSON.parse(JSON.stringify(graphData)); // make deep copy before mutating\n newData = reallocate(graphData, flatlinks);\n const nodes = newData.allocNodes.concat(newData.freeNodes);\n const links = newData.links;\n return {nodes, links}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":499,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":262,"value":"/* Finds directed cycles for given node, link pairs. \n Mutates array of input nodes.\n */\nfunction detectCycles(nodes, links, flatlinks = true) {\n let cycles = [];\n nodes.forEach(function (n) {\n let cycle = findCycle(nodes[n.id], links, flatlinks); \n if (cycle != null) {\n cycle.forEach(function (c) {\n let node = (flatlinks) ? nodes[c.node] : nodes[c.node.id];\n node.alloc = true;\n const item = c.item;\n node.item = item;\n const next = c.li;\n cycles.push({ node, item, next });\n });\n };\n });\n return cycles;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":267,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":363,"value":"testDetectCycle = {\n let testnodes = graph1.nodes;\n let testlinks = JSON.parse(JSON.stringify(graph1.links)); // deep copy\n return detectCycles(testnodes, testlinks, false);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":802,"value":"testFindCycleFlat = {\n const graph2 = iterations.graph2;\n const oldNodes = JSON.parse(JSON.stringify(graph2.nodes));\n const oldLinks = JSON.parse(JSON.stringify(graph2.links));\n return findCycle(oldNodes[9], oldLinks);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1087,"value":"graph1 = {\n const nodes = JSON.parse(JSON.stringify(data.nodes));\n const links = generateLinks(nodes);\n const graphData = {nodes,links};\n detectCycles(nodes,links);\n return graphData;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":401,"value":"function generateLinks(nodes, flatlinks = true) {\n let edges = [];\n if (flatlinks) {\n nodes.forEach( function(n) {\n const source = n.id;\n const target = n.rank[findRankIndex(n.rank, nodes)];\n const value = 1;\n const inCycle = false;\n edges.push({source, target, inCycle, value});\n }); \n } else {\n nodes.forEach( function(n) {\n const source = n;\n const targetId = n.rank[findRankIndex(n.rank, nodes)];\n let target = n;\n nodes.forEach( function(t) { \n if (t.id == targetId) {\n target = t;\n }\n });\n const value = 1;\n const inCycle = false;\n edges.push({source, target, inCycle, value});\n }); \n };\n return edges;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":575,"value":"findRankIndex = (ranks, nodes) => {\n let index = 0;\n let found = false;\n for (let i = 0; i < ranks.length; i++) {\n nodes.forEach( function(n) {\n if (n.id == ranks[i]) {\n index = i;\n found = true;\n return;\n }\n });\n if (found) { return index };\n };\n return index;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":555,"value":"nodes = data.nodes","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"data = FileAttachment(\"desires@9.json\").json()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1415,"value":"function linkArc(d) {\n const r = Math.hypot(d.target.x - d.source.x, d.target.y - d.source.y);\n return `\n M${d.source.x},${d.source.y}\n A${r},${r} 0 0,1 ${d.target.x},${d.target.y}\n `;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1412,"value":"function convertData(data) {\n let data2 = JSON.parse(JSON.stringify(data));\n let nodes = data.nodes;\n let index = 0;\n nodes.forEach(function (n) { \n let rank = [];\n let len = n.rank.length;\n for (let i = 0; i < len - 1; i++) {\n let source = n.rank[i].toString();\n let target = n.rank[i + 1].toString();\n let index = i\n rank.push({ source, target, index });\n }\n data2.nodes[index].rank = rank;\n data2.nodes[index].id = data2.nodes[index].id.toString()\n index = index + 1;\n\n });\n return data2;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1144,"value":"outline = d => {\n return (d.alloc) ? \"#458B00\" : \"#8B0000\";\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"color = {\n const scale = d3.scaleOrdinal(d3.schemePastel2);\n return d => scale(d.group);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":76,"value":"drag = simulation => {\n \n function dragstarted(d) {\n if (!d3.event.active) simulation.alphaTarget(0.3).restart();\n d.fx = d.x;\n d.fy = d.y;\n }\n \n function dragged(d) {\n d.fx = d3.event.x;\n d.fy = d3.event.y;\n }\n \n function dragended(d) {\n if (!d3.event.active) simulation.alphaTarget(0);\n d.fx = null;\n d.fy = null;\n }\n \n return d3.drag()\n .on(\"start\", dragstarted)\n .on(\"drag\", dragged)\n .on(\"end\", dragended);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"height = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1420,"value":"EMOTICONS = [\n {\n \"child\": [\"👶\", \"👶🏻\", \"👶🏼\", \"👶🏽\", \"👶🏾\", \"👶🏿\"],\n \"heart\": [\"🧡\", \"💚\", \"💜\", \"💛\", \"🤍\", \"🤎\", \"💙\", \"🖤\"]\n }\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3d","stdlib":"1","titling":"auto"}} 34:"$33:body"