2b:null 2c:["$","title",null,{"children":"D3 Graph Layout | Chris North | Observable"}] 31:[{"id":"d052aab63b560a567148976b3573bd8c5629d0c8abd600aa7b49f80606cc99bfc1f378400bae48bcf82363691710199a37479333b7e1a377b252488fe651a86d","href":"https://static.observableusercontent.com/files/d052aab63b560a567148976b3573bd8c5629d0c8abd600aa7b49f80606cc99bfc1f378400bae48bcf82363691710199a37479333b7e1a377b252488fe651a86d","name":"flare.csv","type":"text/csv","lastModified":1666760026418.375,"size":7989},{"id":"a54fa5363b4035634b31bda01f902f2620a54a6366986631347558458e2484388de6575e5015e38bccc7db6637d87f80ad4ed7bdcab81ec3f31b75908a22a42d","href":"https://static.observableusercontent.com/files/a54fa5363b4035634b31bda01f902f2620a54a6366986631347558458e2484388de6575e5015e38bccc7db6637d87f80ad4ed7bdcab81ec3f31b75908a22a42d","name":"miserables.json","type":"application/json","lastModified":1666760026418.375,"size":18844}] 2f:{"id":"6a956d6f36652721","slug":"d3-graph-layout","title":"D3 Graph Layout","thumbnail":"4a1edf23871a32c7162a3a5e11de1da4ae99f7dccc0ed9a7ecfe5a49eee5d219","access_level":"public","create_time":"$D2022-10-26T04:53:46.418Z","update_time":"$D2023-10-23T20:38:42.484Z","view_time":null,"first_public_time":"$D2022-10-26T06:01:45.913Z","fork":{"id":"55d94e4867d32ced","slug":"d3-graph-layout-solutions","title":"D3 Graph Layout (solutions)","owner":{"id":"944d12de66c65f0a","login":"chrislnorth","name":"Chris North"}},"stars":0,"starred":false,"owner":{"type":"team","id":"944d12de66c65f0a","login":"chrislnorth","name":"Chris North","avatar_url":"https://avatars-next.observableusercontent.com/4ccf47b2182cd891232f3949528d386f98cf55e9749ceb65960723d6b963c5a2","tier":"starter_2024"},"version":448,"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}],"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":41,"collection":{"id":"9aa1bc9d4b544fec","slug":"vt-cs-5764","title":"VT CS 5764 Lecture Notes","owner":{"id":"944d12de66c65f0a","login":"chrislnorth","name":"Chris North"}},"type":"notebook","body":{"title":"D3 Graph Layout","cells":[{"id":0,"value":"# D3 Graph Layout\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","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","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","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","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","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$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","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","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","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","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","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","output":"","database":"$undefined"},{"id":117,"value":"simulation = {\n let sim = d3\n .forceSimulation(graph.nodes)\n // insert forces here...\n\n // Hookes law:\n\n // Coulomb's law:\n\n // Any other useful forces?\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","output":"$undefined","database":"$undefined"},{"id":415,"value":"viewof button = Inputs.button(\"Click me\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":347,"value":"### D3 graph visualization","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":104,"value":"chart = {\n const svg = d3\n .create(\"svg\")\n .attr(\"width\", width)\n .attr(\"height\", height)\n .style(\"border\", \"1px solid lightgrey\");\n\n // Map edges to lines\n const links = svg\n .append(\"g\")\n .attr(\"stroke\", \"lightgrey\")\n .attr(\"stroke-width\", 1); //...\n\n // Map vertices to circles\n const nodes = svg.append(\"g\").attr(\"fill\", \"steelblue\"); //...\n setupDrag(svg, nodes, simulation);\n\n // Callback after every iteration of the simulation, set xy using values computed by force Simulation\n function update() {\n // make updates here...\n }\n\n return svg.node();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"// Set the fx,fy values of the dragged node to fix it to the mouse position.\n// Force simulation will not move nodes with fx,fy set, and will fix x=fx, y=fy.\nfunction setupDrag(svg, nodes, simulation) {\n // D3 Drag API\n const drag = d3\n .drag()\n .on(\"start\", dragstart)\n .on(\"drag\", dragging)\n .on(\"end\", dragend);\n nodes.call(drag);\n\n // Drag event callback functions\n function dragstart(event) {\n //if (!event.active) // only needed in multi-touch scenarios\n simulation.alphaTarget(0.3).restart(); // restart the sim and run indefinitely\n // do stuff here...\n }\n function dragging(event) {\n // do stuff here...\n }\n function dragend(event) {\n //if (!event.active) // only needed in multi-touch scenarios\n simulation.alphaTarget(0); // return to normal sim stopping condition\n // do stuff here...\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":107,"value":"height = 700","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 30:"$2f:body"