2c:null 2d:["$","title",null,{"children":"D3 Graph Layout (solutions) | Chris North | Observable"}] 32:T518,chart = { const svg = d3 .create("svg") .attr("width", width) .attr("height", height) .style("border", "1px solid lightgrey"); // Map edges to lines const links = svg .append("g") .attr("stroke", "lightgrey") .attr("stroke-width", 1) .selectAll("line") .data(graph.links) .join("line"); //.attr("x1", (e) => e.source.x) //.attr("y1", (e) => e.source.y) //.attr("x2", (e) => e.target.x) //.attr("y2", (e) => e.target.y); // Map vertices to circles const nodes = svg .append("g") .attr("fill", "steelblue") .selectAll("circle") .data(graph.nodes) .join("circle") .attr("r", 5); //.attr("cx", (v) => v.x) //.attr("cy", (v) => v.y); nodes.append("title").text((d) => d.id); setupDrag(svg, nodes, simulation); // Callback after every iteration of the simulation, set xy using values computed by force Simulation function update() { // make updates here... nodes.attr("cx", (v) => v.x).attr("cy", (v) => v.y); links .attr("x1", (e) => e.source.x) .attr("y1", (e) => e.source.y) .attr("x2", (e) => e.target.x) .attr("y2", (e) => e.target.y); } simulation.on("tick", update); update(); // call it once now to set locations if the sim is already done return svg.node(); }33:T42b,// Set the fx,fy values of the dragged node to fix it to the mouse position. // Force simulation will not move nodes with fx,fy set, and will fix x=fx, y=fy. function setupDrag(svg, nodes, simulation) { // D3 Drag API const drag = d3 .drag() .on("start", dragstart) .on("drag", dragging) .on("end", dragend); nodes.call(drag); // Drag event callback functions function dragstart(event) { // do stuff here... //if (!event.active) // only needed in multi-touch scenarios simulation.alphaTarget(0.3).restart(); // restart the sim and run indefinitely event.subject.fx = event.subject.x; event.subject.fy = event.subject.y; } function dragging(event) { // do stuff here... event.subject.fx = event.x; event.subject.fy = event.y; } function dragend(event) { // do stuff here... //if (!event.active) // only needed in multi-touch scenarios simulation.alphaTarget(0); // return to normal sim stopping condition event.subject.fx = null; // release the fix event.subject.fy = null; } }34:[{"id":"d052aab63b560a567148976b3573bd8c5629d0c8abd600aa7b49f80606cc99bfc1f378400bae48bcf82363691710199a37479333b7e1a377b252488fe651a86d","href":"https://static.observableusercontent.com/files/d052aab63b560a567148976b3573bd8c5629d0c8abd600aa7b49f80606cc99bfc1f378400bae48bcf82363691710199a37479333b7e1a377b252488fe651a86d","name":"flare.csv","type":"text/csv","lastModified":1666754741326.018,"size":7989},{"id":"a54fa5363b4035634b31bda01f902f2620a54a6366986631347558458e2484388de6575e5015e38bccc7db6637d87f80ad4ed7bdcab81ec3f31b75908a22a42d","href":"https://static.observableusercontent.com/files/a54fa5363b4035634b31bda01f902f2620a54a6366986631347558458e2484388de6575e5015e38bccc7db6637d87f80ad4ed7bdcab81ec3f31b75908a22a42d","name":"miserables.json","type":"application/json","lastModified":1666755211665.985,"size":18844}] 30:{"id":"55d94e4867d32ced","slug":"d3-graph-layout-solutions","title":"D3 Graph Layout (solutions)","thumbnail":"23c3135a71d3012967f3c7a59c4b4db552a721df0a0ae53f9c56933461decbc9","access_level":"public","create_time":"$D2020-11-04T01:57:26.751Z","update_time":"$D2023-10-23T20:38:27.852Z","view_time":null,"first_public_time":"$D2020-11-04T18:31:31.763Z","has_unpublished_edits":null,"fork":false,"stars":1,"starred":false,"owner":{"type":"team","id":"944d12de66c65f0a","login":"chrislnorth","name":"Chris North","avatar_url":"https://avatars-next.observableusercontent.com/4ccf47b2182cd891232f3949528d386f98cf55e9749ceb65960723d6b963c5a2","tier":"starter_2024","bio":"Department of Computer Science, Virginia Tech"},"version":465,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"2bd52d2c49b80248","login":"chrislnorth","name":"Chris North","avatar_url":"https://avatars-next.observableusercontent.com/4ccf47b2182cd891232f3949528d386f98cf55e9749ceb65960723d6b963c5a2","tier":null,"bio":"Department of Computer Science, Virginia Tech"}],"members":[{"type":"individual","id":"2bd52d2c49b80248","login":"chrislnorth","name":"Chris North","avatar_url":"https://avatars-next.observableusercontent.com/4ccf47b2182cd891232f3949528d386f98cf55e9749ceb65960723d6b963c5a2","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":30,"collection":{"id":"9aa1bc9d4b544fec","slug":"vt-cs-5764","title":"VT CS 5764 Lecture Notes","owner":{"id":"944d12de66c65f0a","login":"chrislnorth","name":"Chris North"}},"type":"notebook","body":{"titling":"auto","title":"D3 Graph Layout (solutions)","cells":[{"id":0,"value":"# D3 Graph Layout (solutions)\n\nVirginia Tech, CS 5764 InfoVis, Lecture Notes by Dr. Chris North\n\nCovers topics from Murray, \"[Interactive Data Visualization for the Web](https://www.oreilly.com/library/view/interactive-data-visualization/9781491921296/)\", Chapter 13.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":2,"value":"## Force-directed graph layout model\n\n* Algorithm for node-link visualization of graphs\n* Example: https://observablehq.com/@d3/force-directed-graph\n* Theory: http://cs.brown.edu/people/rtamassi/gdhandbook/chapters/force-directed.pdf\n\n### Layout optimization criteria (Goal)\n1. Edges are a consistent short length, as much as possible\n2. Vertex pairs with no edge should be far apart, as much as possible\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":333,"value":"### Physics-based model\n1. Model edge links as springs that have a consistent short resting length\n\n [Hooke's Law](https://en.wikipedia.org/wiki/Hooke%27s_law)\n \n ${tex`F_s = (d - L)k_s`}\n\n ${tex`F_s = `} spring force (positive=pull, negative=push)
\n ${tex`d = `} spring length
\n ${tex`L = `} spring resting length
\n ${tex`k_s = `} spring strength constant\n\n3. Model unlinked pairs of nodes as charged particles that repel each other\n\n [Coulomb's Law](https://en.wikipedia.org/wiki/Coulomb%27s_law)\n\n ${tex`F_c = \\large\\frac{-k_c}{d^2}`}\n \n ${tex`F_c = `} charge force (negative=repel)
\n ${tex`k_c = `} charge strength and polarity
\n ${tex`d = `} distance between particles\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":6,"value":"### Mathematical formulation\n\nSum up the force vectors on each node.\n\n> ${tex`\\overrightarrow{F(P)} = \\sum_{edge(P,Q)} \\widehat{PQ} (|PQ| - L) k_s + \n \\sum_{\\neg edge(P,Q)} \\widehat{PQ} \\large\\frac{-k_c}{|PQ|^2}`}\n\n> ${tex`\\overrightarrow{F(P)} = `} force vector on node P
\n> ${tex`|PQ| = `} euclidean distance between nodes P and Q
\n> ${tex`\\widehat{PQ} = \\frac{\\overrightarrow{PQ}}{|PQ|} = `} unit vector from node P towards node Q
\n\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":93,"value":"### Algorithm\n* Initialize random node locations P_i\n* delta = 1\n* Repeat until (delta < deltaMin):\n * For each node P_i:\n * P_i += F(P_i) * delta // update node P position based on F(P)\n * delta *= 0.9\n * callback \"tick\"\n\nRunning time: O(n² * iters)\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":147,"value":"### Parameters\n\n* L\n* k_s\n* k_c\n\nParameter demo: https://observablehq.com/@ee2dev/d3-force-playground\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":141,"value":"## D3 force-directed graph layout\n\n### Data\n* Nodes have IDs\n* Links have source and target node IDs\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":360,"value":"miserables = {\n let g = await FileAttachment(\"miserables.json\").json();\n g.links.splice(109, 1);\n return g;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":389,"value":"flare = {\n let g = { nodes: await FileAttachment(\"flare.csv\").csv() };\n g.links = g.nodes.map((e) => ({\n source: e.id,\n target: e.id.slice(0, e.id.lastIndexOf(\".\"))\n }));\n g.links.splice(0, 1);\n return g;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":372,"value":"// Choose a dataset. Deep copy the data so we can see what new attributes the Simulation adds.\ngraph = {\n button; // reset the data when clicked\n return JSON.parse(JSON.stringify(miserables));\n return JSON.parse(JSON.stringify(flare));\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"### D3 Force simulator\n\nSimulates various physical forces on data nodes: https://github.com/d3/d3-force#forces\n* Centering - move center of mass of all nodes\n* Collision - avoid node overlaps\n* Link Springs - set distance between node pairs according to links\n* Many-body - repel or attract between all pairs of nodes\n* Positioning - gravity attracts nodes towards given x, y, or radial positions\n\nSimulation iterates and updates the data:\n* Computes 2D locations of nodes in graph.nodes[i].x and .y \n* Changes graph.links[i].source and .target into references to the corresponding graph.nodes objects\n* Programmer can use graph.nodes[i].fx,fy to fix the position of a node\n\nLook at the data above to see how the simulation changed it.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":117,"value":"simulation = {\n let sim = d3\n .forceSimulation(graph.nodes)\n // insert forces here...\n\n // Hookes law:\n .force(\n \"spring\",\n d3\n .forceLink(graph.links)\n .id((v) => v.id)\n //.strength(1)\n .distance(30)\n )\n\n // Coulomb's law:\n .force(\"repel\", d3.forceManyBody().strength(-70))\n\n // Any other useful forces?\n \n // Gravity keeps disconnected components from flying away:\n .force(\"gravityX\", d3.forceX(width / 2).strength(0.05))\n .force(\"gravityY\", d3.forceY(height / 2).strength(0.05))\n \n // Center it on screen:\n .force(\"center\", d3.forceCenter(width / 2, height / 2));\n\n // Terminate the force layout when this cell re-runs.\n invalidation.then(() => sim.stop());\n\n return sim;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":415,"value":"viewof button = Inputs.button(\"Click me\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":347,"value":"### D3 graph visualization","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":104,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"height = 700","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 31:"$30:body"