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).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; }