2b:null 2c:["$","title",null,{"children":"Force edge bundling | Stuart Thompson | Observable"}] 31:T3afe,ForceEdgeBundling = function(){ var data_nodes = {}, // {'nodeid':{'x':,'y':},..} data_edges = [], // [{'source':'nodeid1', 'target':'nodeid2'},..] compatibility_list_for_edge = [], subdivision_points_for_edge = [], K = 0.05, // global bundling constant controling edge stiffness S_initial = 1e-6, // init. distance to move points P_initial = 1, // init. subdivision number P_rate = 4, // subdivision rate increase C = 6, // number of cycles to perform I_initial = 70, // init. number of iterations for cycle I_rate = 0.6667, // rate at which iteration number decreases i.e. 2/3 compatibility_threshold = 0.6, invers_quadratic_mode = false, eps = 1e-6; /*** Geometry Helper Methods ***/ function vector_dot_product(p, q){ return p.x * q.x + p.y * q.y; } function edge_as_vector(P){ return {'x': data_nodes.get(P.target).x - data_nodes.get(P.source).x, 'y': data_nodes.get(P.target).y - data_nodes.get(P.source).y} } function edge_length(e){ return Math.sqrt( Math.pow(data_nodes.get(e.source).x-data_nodes.get(e.target).x, 2) + Math.pow(data_nodes.get(e.source).y-data_nodes.get(e.target).y, 2) ); } function custom_edge_length(e){ return Math.sqrt( Math.pow(e.source.x - e.target.x, 2) + Math.pow(e.source.y - e.target.y, 2)); } function edge_midpoint(e){ var middle_x = (data_nodes.get(e.source).x + data_nodes.get(e.target).x) / 2.0; var middle_y = (data_nodes.get(e.source).y + data_nodes.get(e.target).y) / 2.0; return {'x': middle_x, 'y': middle_y}; } function compute_divided_edge_length(e_idx){ var length = 0; for(var i = 1; i < subdivision_points_for_edge[e_idx].length; i++){ var segment_length = euclidean_distance( subdivision_points_for_edge[e_idx][i], subdivision_points_for_edge[e_idx][i-1] ); length += segment_length; } return length; } function euclidean_distance(p, q){ return Math.sqrt( Math.pow(p.x-q.x, 2) + Math.pow(p.y-q.y, 2) ); } function project_point_on_line(p, Q){ var L = Math.sqrt( (Q.target.x - Q.source.x) * (Q.target.x - Q.source.x) + (Q.target.y - Q.source.y) * (Q.target.y - Q.source.y)); var r = ((Q.source.y - p.y) * (Q.source.y - Q.target.y) - (Q.source.x - p.x) * (Q.target.x - Q.source.x)) / (L * L); return {'x':(Q.source.x + r * (Q.target.x - Q.source.x)), 'y':(Q.source.y + r * (Q.target.y - Q.source.y))}; } function initialize_edge_subdivisions(){ for(var i = 0; i < data_edges.length; i++) // for each edge if(P_initial == 1) subdivision_points_for_edge[i] = []; // no subdivision points else{ subdivision_points_for_edge[i] = []; // for edge i, add x, y of edge i's source and target to array?? subdivision_points_for_edge[i].push(data_nodes[data_edges[i].source]); subdivision_points_for_edge[i].push(data_nodes[data_edges[i].target]); } } function initialize_compatibility_lists(){ for(var i = 0; i < data_edges.length; i++) compatibility_list_for_edge[i] = []; //0 compatible edges. } function filter_self_loops(edgelist){ var filtered_edge_list = []; for(var e=0; e < edgelist.length; e++){ if(data_nodes.get(edgelist[e].source) && data_nodes.get(edgelist[e].source).x != data_nodes.get(edgelist[e].target).x && data_nodes.get(edgelist[e].source).y != data_nodes.get(edgelist[e].target).y ){ //or smaller than eps filtered_edge_list.push(edgelist[e]); } } return filtered_edge_list; } /*** Force Calculation Methods ***/ function apply_spring_force(e_idx, i, kP){ // e_idx, edge index // i, id for segment, starting 1 // kp, local spring contant var prev = subdivision_points_for_edge[e_idx][i-1]; var next = subdivision_points_for_edge[e_idx][i+1]; var crnt = subdivision_points_for_edge[e_idx][i]; var x = prev.x - crnt.x + next.x - crnt.x; var y = prev.y - crnt.y + next.y - crnt.y; x *= kP; y *= kP; return {'x' : x, 'y' : y}; } function apply_electrostatic_force(e_idx, i , S){ // S is how much to move a point // i is index for segment, starting 1 var sum_of_forces = { 'x' : 0, 'y' : 0}; // find compatible edges for the given edge, [1,6,8] var compatible_edges_list = compatibility_list_for_edge[e_idx]; // what is window.sbd? window.sbd = subdivision_points_for_edge; for(var oe = 0; oe < compatible_edges_list.length; oe++){ // for each compatiple edge of the given edge // compatible_edges_list[oe] is the id for that compatible edge // and then get the list of subdivision points for that edge var force = { 'x': subdivision_points_for_edge[compatible_edges_list[oe]][i].x - subdivision_points_for_edge[e_idx][i].x, 'y': subdivision_points_for_edge[compatible_edges_list[oe]][i].y - subdivision_points_for_edge[e_idx][i].y}; if((Math.abs(force.x) > eps)||(Math.abs(force.y) > eps)){ // essentially inverse of distance between two points var diff = ( 1 / Math.pow(custom_edge_length({'source':subdivision_points_for_edge[compatible_edges_list[oe]][i], 'target':subdivision_points_for_edge[e_idx][i]}),1)); // accumulating forces exerted by points on // all compatible edges to the point of the given edge sum_of_forces.x += force.x*diff; sum_of_forces.y += force.y*diff; } } return sum_of_forces; } function apply_resulting_forces_on_subdivision_points(e_idx, P, S){ var kP = K/(edge_length(data_edges[e_idx])*(P+1)); // kP=K/(|P| * (number of segments)), where |P| is the initial length of edge P. // kp is identical for each segment of P, it is a local spring constant // (length * (num of sub division pts - 1)) var resulting_forces_for_subdivision_points = [{'x':0, 'y':0}]; for(var i = 1; i < P+1; i++){ // for each subdivision points, excluding initial and end points var resulting_force = {'x' : 0, 'y' : 0}; // spring_force in {'x' : x, 'y' : y} var spring_force = apply_spring_force(e_idx, i, kP); // similar format {'x' : x, 'y' : y} var electrostatic_force = apply_electrostatic_force(e_idx, i, S); // combine all forces resulting_force.x = S*(spring_force.x + electrostatic_force.x); resulting_force.y = S*(spring_force.y + electrostatic_force.y); resulting_forces_for_subdivision_points.push(resulting_force); } resulting_forces_for_subdivision_points.push({'x':0, 'y':0}); // [{'x':0, 'y':0}, {'x':0, 'y':0}, {'x':0, 'y':0},...] // each dict is return resulting_forces_for_subdivision_points; } /*** ********************** ***/ /*** Edge Division Calculation Methods ***/ function update_edge_divisions(P){ for(var e_idx=0; e_idx < data_edges.length; e_idx++){ if( P == 1 ){ subdivision_points_for_edge[e_idx].push(data_nodes.get(data_edges[e_idx].source)); // source subdivision_points_for_edge[e_idx].push(edge_midpoint(data_edges[e_idx])); // mid point subdivision_points_for_edge[e_idx].push(data_nodes.get(data_edges[e_idx].target)); // target }else{ var divided_edge_length = compute_divided_edge_length(e_idx); // add up segment lengths var segment_length = divided_edge_length / (P+1); // get average segment length var current_segment_length = segment_length; var new_subdivision_points = []; // initiate a new array for subdivision points new_subdivision_points.push(data_nodes.get(data_edges[e_idx].source)); //source for(var i = 1; i < subdivision_points_for_edge[e_idx].length; i++){ var old_segment_length = euclidean_distance(subdivision_points_for_edge[e_idx][i], subdivision_points_for_edge[e_idx][i-1]); while(old_segment_length > current_segment_length){ var percent_position = current_segment_length / old_segment_length; var new_subdivision_point_x = subdivision_points_for_edge[e_idx][i-1].x; var new_subdivision_point_y = subdivision_points_for_edge[e_idx][i-1].y; new_subdivision_point_x += percent_position*(subdivision_points_for_edge[e_idx][i].x - subdivision_points_for_edge[e_idx][i-1].x); new_subdivision_point_y += percent_position*(subdivision_points_for_edge[e_idx][i].y - subdivision_points_for_edge[e_idx][i-1].y); new_subdivision_points.push({'x':new_subdivision_point_x, 'y':new_subdivision_point_y }); old_segment_length -= current_segment_length; current_segment_length = segment_length; } current_segment_length -= old_segment_length; } new_subdivision_points.push(data_nodes.get(data_edges[e_idx].target)); //target subdivision_points_for_edge[e_idx] = new_subdivision_points; } } } /*** ********************** ***/ /*** Edge compatibility measures ***/ function angle_compatibility(P, Q){ var result = Math.abs(vector_dot_product(edge_as_vector(P),edge_as_vector(Q))/(edge_length(P)*edge_length(Q))); return result; } function scale_compatibility(P, Q){ var lavg = (edge_length(P) + edge_length(Q))/2.0; var result = 2.0/(lavg/Math.min(edge_length(P),edge_length(Q)) + Math.max(edge_length(P), edge_length(Q))/lavg); return result; } function position_compatibility(P, Q){ var lavg = (edge_length(P) + edge_length(Q))/2.0; var midP = {'x':(data_nodes.get(P.source).x + data_nodes.get(P.target).x)/2.0, 'y':(data_nodes.get(P.source).y + data_nodes.get(P.target).y)/2.0}; var midQ = {'x':(data_nodes.get(Q.source).x + data_nodes.get(Q.target).x)/2.0, 'y':(data_nodes.get(Q.source).y + data_nodes.get(Q.target).y)/2.0}; var result = lavg/(lavg + euclidean_distance(midP, midQ)); return result; } function edge_visibility(P, Q){ var I0 = project_point_on_line(data_nodes.get(Q.source), {'source':data_nodes.get(P.source), 'target':data_nodes.get(P.target)}); var I1 = project_point_on_line(data_nodes.get(Q.target), {'source':data_nodes.get(P.source), 'target':data_nodes.get(P.target)}); //send acutal edge points positions var midI = {'x':(I0.x + I1.x)/2.0, 'y':(I0.y + I1.y)/2.0}; var midP = {'x':(data_nodes.get(P.source).x + data_nodes.get(P.target).x)/2.0, 'y':(data_nodes.get(P.source).y + data_nodes.get(P.target).y)/2.0}; var result = Math.max(0, 1 - 2 * euclidean_distance(midP,midI)/euclidean_distance(I0,I1)); return result; } function visibility_compatibility(P, Q){ return Math.min(edge_visibility(P,Q), edge_visibility(Q,P)); } function compatibility_score(P, Q){ var result = (angle_compatibility(P,Q) * scale_compatibility(P,Q) * position_compatibility(P,Q) * visibility_compatibility(P,Q)); return result; } function are_compatible(P, Q){ //console.log('compatibility ' + P.source +' - '+ P.target + ' and ' + Q.source +' '+ Q.target); return (compatibility_score(P,Q) >= compatibility_threshold); } function compute_compatibility_lists() { for(var e = 0; e < data_edges.length - 1; e++){ for(var oe = e + 1 ; oe < data_edges.length; oe++){ // don't want any duplicates if(e == oe) continue; else{ if(are_compatible(data_edges[e],data_edges[oe])){ compatibility_list_for_edge[e].push(oe); compatibility_list_for_edge[oe].push(e); } } } } } /*** ************************ ***/ /*** Main Bundling Loop Methods ***/ var forcebundle = function(){ var S = S_initial; // how much to move a point var I = I_initial; // num of iterations per cycle/ what is a cycle? var P = P_initial; // number of sub-points on an edge initialize_edge_subdivisions(); /// [[source.id, target.id], [], [],...] initialize_compatibility_lists(); // [[],[],...] update_edge_divisions(P); // if P is one, we just add a mid-point to each list // [[source.id, midpoint, target.id],[],...] compute_compatibility_lists(); for(var cycle=0; cycle < C; cycle++){ for (var iteration = 0; iteration < I; iteration++){ // in each iteration var forces = []; for(var edge = 0; edge < data_edges.length; edge++){ // for edge 'edge', number of subpoints P, and movement S // get [{'x':0, 'y':0}, {'x':0, 'y':0}, {'x':0, 'y':0},...] forces[edge] = apply_resulting_forces_on_subdivision_points(edge, P, S); } for(var e = 0; e < data_edges.length; e++){ // for each edge for(var i=0; i < P + 1;i++){ subdivision_points_for_edge[e][i].x += forces[e][i].x; subdivision_points_for_edge[e][i].y += forces[e][i].y; } } } //prepare for next cycle S = S / 2; P = P * 2; I = I_rate * I; update_edge_divisions(P); console.log('C' + cycle); console.log('P' + P); console.log('S' + S); } return subdivision_points_for_edge; } /*** ************************ ***/ /*** Getters/Setters Methods ***/ forcebundle.nodes = function(nl){ if(arguments.length == 0){ return data_nodes; } else{ data_nodes = nl; } return forcebundle; } forcebundle.edges = function(ll){ if(arguments.length == 0){ return data_edges; } else{ data_edges = filter_self_loops(ll); //remove edges to from to the same point } return forcebundle; } forcebundle.bundling_stiffness = function(k){ if(arguments.length == 0){ return K; } else{ K = k; } return forcebundle; } forcebundle.step_size = function(step){ if(arguments.length == 0){ return S_initial; } else{ S_initial = step; } return forcebundle; } forcebundle.cycles = function(c){ if(arguments.length == 0){ return C; } else{ C = c; } return forcebundle; } forcebundle.iterations = function(i){ if(arguments.length == 0){ return I_initial; } else{ I_initial = i; } return forcebundle; } forcebundle.iterations_rate = function(i){ if(arguments.length == 0){ return I_rate; } else{ I_rate = i; } return forcebundle; } forcebundle.subdivision_points_seed = function(p){ if(arguments.length == 0){ return P; } else{ var P = p; } return forcebundle; } forcebundle.subdivision_rate = function(r){ if(arguments.length == 0){ return P_rate; } else{ P_rate = r; } return forcebundle; } forcebundle.compatbility_threshold = function(t){ if(arguments.length == 0){ return compatibility_threshold; } else{ compatibility_threshold = t; } return forcebundle; } /*** ************************ ***/ return forcebundle; }32:[] 2f:{"id":"8b34b3eb3390018c","slug":"force-edge-bundling","title":"Force edge bundling","thumbnail":"9cdb3477d632617bcb9a9d092627756c70be80efac20825a890994b185ae4bc6","access_level":"public","create_time":"$D2019-03-15T18:30:45.504Z","update_time":"$D2025-04-09T01:51:39.520Z","view_time":null,"first_public_time":"$D2019-03-15T19:21:28.221Z","fork":{"id":"abbede017d738edd","slug":"standalone-function-for-a-graduated-stroke-on-a-curved-path","title":"Standalone function for a graduated stroke on a curved path in D3 ","owner":{"id":"0037882dbfd20f7d","login":"stuartathompson","name":"Stuart Thompson"}},"stars":15,"starred":false,"owner":{"type":"team","id":"0037882dbfd20f7d","login":"stuartathompson","name":"Stuart Thompson","avatar_url":"https://avatars-next.observableusercontent.com/612df2c15ecd79793ae9e1da55f073846192b68a855df3fa08cb20625a22cb61","tier":"starter_2024"},"version":725,"publish_version":725,"role":null,"authored":false,"authors":[{"type":"individual","id":"2f7c0ea43db5e5ea","login":"stuartathompson","name":"Stuart Thompson","avatar_url":"https://avatars-next.observableusercontent.com/612df2c15ecd79793ae9e1da55f073846192b68a855df3fa08cb20625a22cb61","tier":null}],"members":[{"type":"individual","id":"2f7c0ea43db5e5ea","login":"stuartathompson","name":"Stuart Thompson","avatar_url":"https://avatars-next.observableusercontent.com/612df2c15ecd79793ae9e1da55f073846192b68a855df3fa08cb20625a22cb61","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":9,"collection":null,"type":"notebook","body":{"title":"Force edge bundling","cells":[{"id":0,"value":"md`# Force edge bundling`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":526,"value":"md`A demo of [forceEdgeBundling](https://github.com/upphiminn/d3.ForceBundle), which takes source and target nodes and clusters them together. This is especially useful for maps with lots of lines between locations, but probably has many other uses as well.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":676,"value":"html`

Red lines are original connections between source and target. Black lines are the results of the forceEdgeBundling.

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":715,"value":"viewof lines = slider({\n min: 0, \n max: 200, \n step: 1, \n value: 100, \n title: \"Number of lines\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":628,"value":"viewof stiffness = slider({\n min: 0, \n max: 30, \n step: .005, \n value: 4, \n title: \"Stiffness\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":630,"value":"viewof stepSize = slider({\n min: 0.01, \n max: 100, \n step: .01, \n value: 2, \n title: \"Step size\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":517,"value":"viewof replay = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":430,"value":"viz = {\n replay\n // Overall vars\n const margin = 0\n const width = 1000 - margin * 2\n const svgW = d3.select(DOM.svg(width + margin * 2, height + margin * 2))\n \n // Making an SVG\n const svg = svgW.append('g')\n .attr('transform',`translate(${margin},${margin})`)\n\n // The direct links\n svg.selectAll('path')\n .data(directLinks).enter()\n .append('path')\n .attr('d', (d) => {\n return `M ${d.x1},${d.y1} L ${d.x2}, ${d.y2}`\n })\n .attr('stroke', '#DA6F65')\n .attr('stroke-width', '1')\n .attr('opacity', .5)\n \n // Draw the force edged results\n svg.selectAll('path.bundled')\n .data(results).enter()\n .append('path') \n .attr('d', line)\n .attr('stroke', 'black')\n .attr('fill', 'transparent')\n .attr('stroke-width', 1)\n \n return svgW.node() \n \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":685,"value":"md`This works by using the typical force directed data structure with an associative array containing links and nodes.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":689,"value":"md`**Here's what the data input data looks like.**\n\n *Note the nodes array is hashed used d3.map()*\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":687,"value":"{\n return {nodes: d3.map(data, d => d.id), links: data.links}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":704,"value":"md`And here's what you get back from the bundling function – an array of asssociative arrays containing new x/y coordinates for each point along the path.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":706,"value":"results","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":568,"value":"md`### Force Edge Bundling`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":702,"value":"md`Here are the relevant functions. One is a generator that sets the options. The ForceEdgeBundling function is just pasted in below.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":567,"value":"fbundling = (nodes, edges) => {\n var results = ForceEdgeBundling()\n\t\t\t\t.nodes(nodes)\n\t\t\t\t.edges(edges)\n\t\t\t\t.step_size(stepSize)\n\t\t\t\t.bundling_stiffness(stiffness)\n return results()\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":571,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":642,"value":"md`### Data`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":645,"value":"data = {\n replay\n const tempData = {links: [], nodes: [{id: 'anchor', x: width, y: height/2}]}\n \n for(var d of d3.range(0, lines)){\n var higherLower = Math.random() > .5\n var randomX = higherLower ? Math.random()*(width/2) : width/2 + (Math.random()*(width/2))\n var randomY = higherLower ? Math.random()*(height/2) : height/2 + (Math.random()*height/2)\n var linkedTo = Math.round(Math.random()*(lines-1))\n tempData.nodes.push({\n id: 'id-'+d,\n x: randomX,\n y: randomY\n })\n tempData.links.push({\n source: 'id-'+d,\n target: 'anchor'\n })\n }\n return tempData\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":647,"value":"directLinks = {\n var tempLinks = []\n for(var d of data.links){\n var from = parseFloat(d.source.replace('id-', ''))\n var to = parseFloat(d.target.replace('id-', ''))\n tempLinks.push({\n x1: data.nodes[from].x,\n y1: data.nodes[from].y,\n x2: width,\n y2: height/2\n })\n }\n return tempLinks\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":708,"value":"results = {\n // Triggering updates on input change\n stiffness\n stepSize\n \n // Calculate force edge bundling.\n // NOTE! You have to shim hashes onto data.nodes using d3.map()\n return fbundling(d3.map(data.nodes, d => d.id), data.links) \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":639,"value":"md`### Others`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":5,"value":"d3 = require('d3@v5')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":616,"value":"line = d3.line()\n .x(d => d.x)\n .y(d => d.y)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":649,"value":"height = 500","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":632,"value":"import { slider } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 30:"$2f:body"