a now-successful attempt to draw links with canvas paths so that the end of each link overlaps perfectly with the center of an svg circle we use to represent a node.
thanks to @enjalot for pointing out that the CSS body { margin: 0; } would do the trick.
a clue: somehow the canvas links layer lines up nicely with the svg nodes layer in the iframe on bl.ocks.org but doesn’t at all when it’s all by itself on the page 🤔
a fork of Blocks Graph I Readme Mentions
a simpler example of this canvas for links, svg for nodes network drawing technique is the bl.ock Ch. 11, Fig. 10 - D3.js in Action from emeeks
<html>
<head>
<title>Blocks Graph - Readme Mentions</title>
<meta charset="utf-8" />
<script src="https://d3js.org/d3.v3.min.js"></script>
<script src="jsLouvain.js"></script>
<style>
body {
margin:0;
position:fixed;
top:0;
right:0;
bottom:0;
left:0;
}
/*svg { width: 100%; height: 100%; }*/
/* Make the chart container fill the page using CSS */
#viz {
position: fixed;
left: 0px;
right: 0px;
top: 0px;
bottom: 0px;
}
</style>
</head>
<body>
<div id="viz"></div>
<script>
// Extract the width and height that was computed by CSS
var vizDiv = document.getElementById("viz");
var width = vizDiv.clientWidth;
var height = vizDiv.clientHeight;
var minSide = d3.min([width, height]);
var xOffset = (width - minSide) / 2;
var yOffset = (height - minSide) / 2;
// Use the extracted size to set the size of a Canvas element
var canvas = d3.select(vizDiv).append("canvas")
.attr("width", width)
.attr("height", height)
.style('position', 'absolute');
// Use the extracted size to set the size of a SVG element
var svg = d3.select(vizDiv).append("svg")
.attr("width", width)
.attr("height", height)
.classed("main", true)
.style('position', 'absolute');
d3.json("readme-blocks-graph.json", function(error,data) { createNetwork(data) });
function onlyUnique(value, index, self) {
return self.indexOf(value) === index;
}
function createNetwork(graphContainer) {
var nodeHash = {};
var nodes = [];
var edges = [];
var edgelist = graphContainer["graph"]["edges"];
var nodelist = graphContainer["graph"]["nodes"];
edgelist.forEach(function (edge) {
if (!nodeHash[edge.source]) {
nodeHash[edge.source] = {
id: edge.source,
label: edge.source
};
nodes.push(nodeHash[edge.source]);
}
if (!nodeHash[edge.target]) {
nodeHash[edge.target] = {
id: edge.target,
label: edge.target
};
nodes.push(nodeHash[edge.target]);
}
if (edge/*.weight == 5*/) {
edges.push({id: nodeHash[edge.source].id + "-" + nodeHash[edge.target].id, source: nodeHash[edge.source], target: nodeHash[edge.target], weight: 1/*edge.weight*/});
}
});
// get some attributes from the nodelist (calculated elsewhere)
// and store them in the nodeHash
nodelist.forEach(function (node) {
if(nodeHash[node.id]) {
nodeHash[node.id]["user"] = node["user"];
nodeHash[node.id]["createdAt"] = node["createdAt"];
nodeHash[node.id]["updatedAt"] = node["updatedAt"];
nodeHash[node.id]["description"] = node["description"];
}
})
// take the attributes now in the nodeHash
// and hang them on the nodes (calculated here from the edgelist)
nodes.forEach(function (node) {
if(nodeHash[node.id]) {
node["user"] = nodeHash[node.id]["user"];
node["createdAt"] = nodeHash[node.id]["createdAt"];
node["updatedAt"] = nodeHash[node.id]["updatedAt"];
node["description"] = nodeHash[node.id]["description"];
}
})
console.log("nodes", nodes);
console.log("edges", edges);
createForceNetwork(nodes, edges);
}
function modularityCensus(nodes, edges, moduleHash) {
edges.forEach(function (edge) {
if (edge.source.module !== edge.target.module) {
edge.border = true;
}
else {
edge.border = false;
}
});
nodes.forEach(function (node) {
var theseEdges = edges.filter(function(d) {return d.source === node || d.target === node});
var theseSourceModules = theseEdges.map(function (d) {return d.source.module}).filter(onlyUnique);
var theseTargetModules = theseEdges.map(function (d) {return d.target.module}).filter(onlyUnique);
if (theseSourceModules.length > 1 || theseTargetModules.length > 1) {
node.border = true;
}
else {
node.border = false;
}
});
}
function createForceNetwork(nodes, edges, graphContainer) {
//create a network from an edgelist
//var colors = d3.scale.ordinal().domain([0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]).range(["#996666", "#66CCCC", "#FFFF99", "#CC9999", "#666633", "#993300", "#999966", "#660000", "#996699", "#cc6633", "#ff9966", "#339999", "#6699cc", "#ffcc66", "#ff6600", "#00ccccc"]);
var colors = d3.scale.category20();
var node_data = nodes.map(function (d) {return d.id});
var edge_data = edges.map(function (d) {return {source: d.source.id, target: d.target.id, weight: 1}; });
console.log("node_data for jLouvain", node_data);
console.log("edge_data for jLouvain", edge_data);
var community = jLouvain().nodes(node_data).edges(edge_data);
var result = community();
console.log("jLouvain result", result);
nodes.forEach(function (node) {
node.module = result[node.id]
//console.log("node.module", node.module)
});
modularityCensus(nodes, edges, result);
var force = d3.layout.force().nodes(nodes).links(edges)
.size([minSide, minSide]) // make a square
.charge(-100)
.chargeDistance(100)
.linkStrength(2)
.linkDistance(3)
.gravity(0.07);
/*
var edgeEnter = d3.select("svg.main").selectAll("g.edge")
.data(edges, function (d) {return d.id})
.enter()
.append("g")
.attr("class", "edge");
edgeEnter
.append("line")
.style("stroke-width", "1px")
.style("stroke", "gray")
.style("pointer-events", "none");
*/
var nodeEnter = d3.select("svg.main").selectAll("g.node")
.data(nodes, function (d) {return d.id})
.enter();
nodeEnter
.append("a")
.attr("xlink:href", function (d) {
return "//bl.ocks.org/" + d.user + "/" + d.id;
})
//.attr("target", "_blank")
.append("circle")
.attr("r", 3)
.attr("class", "foreground")
.style("fill", function (d) {return colors(d.module)})
.style("stroke-width", function (d) {return d.border ? "3px" : "1px"})
/*
// draw labels over nodes
nodeEnter.append("text")
.style("text-anchor", "middle")
.attr("y", 3)
.style("stroke-width", "1px")
.style("stroke-opacity", 0.75)
.style("stroke", "white")
.style("font-size", "8px")
.text(function (d) {return d.id})
.style("pointer-events", "none")
nodeEnter.append("text")
.style("text-anchor", "middle")
.attr("y", 3)
.style("font-size", "8px")
.text(function (d) {return d.id})
.style("pointer-events", "none")
*/
force.start();
for(var i = 0; i < 200; i++){
force.tick();
}
//force.on("tick", updateNetwork);
// after 200 iterations, we say the network
// has stabilized and we stop the
// force layout physics simulation
force.stop();
// now we draw the network
updateNetwork(edges);
function updateNetwork(edges) {
// // draw the links
// d3.select("svg.main").selectAll("line")
// .attr("x1", function (d) {return d.source.x})
// .attr("y1", function (d) {return d.source.y})
// .attr("x2", function (d) {return d.target.x})
// .attr("y2", function (d) {return d.target.y})
// .attr("transform", "translate(" + xOffset + "," + yOffset +")");
var context = d3.select("canvas").node().getContext("2d");
context.clearRect(0, 0, width, height);
context.translate(xOffset, yOffset);
// draw links (or edges, if you prefer)
context.strokeStyle = "rgba(0, 0, 0, 0.5)";
context.beginPath();
edges.forEach(function(d) {
context.moveTo(d.source.x, d.source.y);
context.lineTo(d.target.x, d.target.y);
});
context.stroke();
// draw the nodes
d3.select("svg.main").selectAll("circle")
.attr("cx", function (d) {return d.x; })
.attr("cy", function (d) {return d.y; })
.attr("transform", "translate(" + xOffset + "," + yOffset +")");
}
}
</script>
</body>
</html>/*
Author: Corneliu S. (github.com/upphiminn)
This is a javascript implementation of the Louvain
community detection algorithm (http://arxiv.org/abs/0803.0476)
Based on https://bitbucket.org/taynaud/python-louvain/overview
*/
(function(){
jLouvain = function(){
//Constants
var __PASS_MAX = -1
var __MIN = 0.0000001
//Local vars
var original_graph_nodes;
var original_graph_edges;
var original_graph = {};
var partition_init;
//Helpers
function make_set(array){
var set = {};
array.forEach(function(d,i){
set[d] = true;
});
return Object.keys(set);
};
function obj_values(obj){
var vals = [];
for( var key in obj ) {
if ( obj.hasOwnProperty(key) ) {
vals.push(obj[key]);
}
}
return vals;
};
function get_degree_for_node(graph, node){
var neighbours = graph._assoc_mat[node] ? Object.keys(graph._assoc_mat[node]) : [];
var weight = 0;
neighbours.forEach(function(neighbour,i){
var value = graph._assoc_mat[node][neighbour] || 1;
if(node == neighbour)
value *= 2;
weight += value;
});
return weight;
};
function get_neighbours_of_node(graph, node){
if(typeof graph._assoc_mat[node] == 'undefined')
return [];
var neighbours = Object.keys(graph._assoc_mat[node]);
return neighbours;
}
function get_edge_weight(graph, node1, node2){
return graph._assoc_mat[node1] ? graph._assoc_mat[node1][node2] : undefined;
}
function get_graph_size(graph){
var size = 0;
graph.edges.forEach(function(edge){
size += edge.weight;
});
return size;
}
function add_edge_to_graph(graph, edge){
update_assoc_mat(graph, edge);
var edge_index = graph.edges.map(function(d){
return d.source+'_'+d.target;
}).indexOf(edge.source+'_'+edge.target);
if(edge_index != -1)
graph.edges[edge_index].weight = edge.weight;
else
graph.edges.push(edge);
}
function make_assoc_mat(edge_list){
var mat = {};
edge_list.forEach(function(edge, i){
mat[edge.source] = mat[edge.source] || {};
mat[edge.source][edge.target] = edge.weight;
mat[edge.target] = mat[edge.target] || {};
mat[edge.target][edge.source] = edge.weight;
});
return mat;
}
function update_assoc_mat(graph, edge){
graph._assoc_mat[edge.source] = graph._assoc_mat[edge.source] || {};
graph._assoc_mat[edge.source][edge.target] = edge.weight;
graph._assoc_mat[edge.target] = graph._assoc_mat[edge.target] || {};
graph._assoc_mat[edge.target][edge.source] = edge.weight;
}
function clone(obj){
if(obj == null || typeof(obj) != 'object')
return obj;
var temp = obj.constructor();
for(var key in obj)
temp[key] = clone(obj[key]);
return temp;
}
//Core-Algorithm Related
function init_status(graph, status, part){
status['nodes_to_com'] = {};
status['total_weight'] = 0;
status['internals'] = {};
status['degrees'] = {};
status['gdegrees'] = {};
status['loops'] = {};
status['total_weight'] = get_graph_size(graph);
if(typeof part == 'undefined'){
graph.nodes.forEach(function(node,i){
status.nodes_to_com[node] = i;
var deg = get_degree_for_node(graph, node);
if (deg < 0)
throw 'Bad graph type, use positive weights!';
status.degrees[i] = deg;
status.gdegrees[node] = deg;
status.loops[node] = get_edge_weight(graph, node, node) || 0;
status.internals[i] = status.loops[node];
});
}else{
graph.nodes.forEach(function(node,i){
var com = part[node];
status.nodes_to_com[node] = com;
var deg = get_degree_for_node(graph, node);
status.degrees[com] = (status.degrees[com] || 0) + deg;
status.gdegrees[node] = deg;
var inc = 0.0;
var neighbours = get_neighbours_of_node(graph, node);
neighbours.forEach(function(neighbour, i){
var weight = graph._assoc_mat[node][neighbour];
if (weight <= 0){
throw "Bad graph type, use positive weights";
}
if(part[neighbour] == com){
if (neighbour == node){
inc += weight;
}else{
inc += weight/2.0;
}
}
});
status.internals[com] = (status.internals[com] || 0) + inc;
});
}
}
function __modularity(status){
var links = status.total_weight;
var result = 0.0;
var communities = make_set(obj_values(status.nodes_to_com));
communities.forEach(function(com,i){
var in_degree = status.internals[com] || 0 ;
var degree = status.degrees[com] || 0 ;
if(links > 0){
result = result + in_degree / links - Math.pow((degree / (2.0*links)), 2);
}
});
return result;
}
function __neighcom(node, graph, status){
// compute the communities in the neighb. of the node, with the graph given by
// node_to_com
var weights = {};
var neighboorhood = get_neighbours_of_node(graph, node);//make iterable;
neighboorhood.forEach(function(neighbour, i){
if(neighbour != node){
var weight = graph._assoc_mat[node][neighbour] || 1;
var neighbourcom = status.nodes_to_com[neighbour];
weights[neighbourcom] = (weights[neighbourcom] || 0) + weight;
}
});
return weights;
}
function __insert(node, com, weight, status){
//insert node into com and modify status
status.nodes_to_com[node] = +com;
status.degrees[com] = (status.degrees[com] || 0) + (status.gdegrees[node]||0);
status.internals[com] = (status.internals[com] || 0) + weight + (status.loops[node]||0);
}
function __remove(node, com, weight, status){
//remove node from com and modify status
status.degrees[com] = ((status.degrees[com] || 0) - (status.gdegrees[node] || 0));
status.internals[com] = ((status.internals[com] || 0) - weight -(status.loops[node] ||0));
status.nodes_to_com[node] = -1;
}
function __renumber(dict){
var count = 0;
var ret = clone(dict); //deep copy :)
var new_values = {};
var dict_keys = Object.keys(dict);
dict_keys.forEach(function(key){
var value = dict[key];
var new_value = typeof new_values[value] =='undefined' ? -1 : new_values[value];
if(new_value == -1){
new_values[value] = count;
new_value = count;
count = count + 1;
}
ret[key] = new_value;
});
return ret;
}
function __one_level(graph, status){
//Compute one level of the Communities Dendogram.
var modif = true,
nb_pass_done = 0,
cur_mod = __modularity(status),
new_mod = cur_mod;
while (modif && nb_pass_done != __PASS_MAX){
cur_mod = new_mod;
modif = false;
nb_pass_done += 1
graph.nodes.forEach(function(node,i){
var com_node = status.nodes_to_com[node];
var degc_totw = (status.gdegrees[node] || 0) / (status.total_weight * 2.0);
var neigh_communities = __neighcom(node, graph, status);
__remove(node, com_node, (neigh_communities[com_node] || 0.0), status);
var best_com = com_node;
var best_increase = 0;
var neigh_communities_entries = Object.keys(neigh_communities);//make iterable;
neigh_communities_entries.forEach(function(com,i){
var incr = neigh_communities[com] - (status.degrees[com] || 0.0) * degc_totw;
if (incr > best_increase){
best_increase = incr;
best_com = com;
}
});
__insert(node, best_com, neigh_communities[best_com] || 0, status);
if(best_com != com_node)
modif = true;
});
new_mod = __modularity(status);
if(new_mod - cur_mod < __MIN)
break;
}
}
function induced_graph(partition, graph){
var ret = {nodes:[], edges:[], _assoc_mat: {}};
var w_prec, weight;
//add nodes from partition values
var partition_values = obj_values(partition);
ret.nodes = ret.nodes.concat(make_set(partition_values)); //make set
graph.edges.forEach(function(edge,i){
weight = edge.weight || 1;
var com1 = partition[edge.source];
var com2 = partition[edge.target];
w_prec = (get_edge_weight(ret, com1, com2) || 0);
var new_weight = (w_prec + weight);
add_edge_to_graph(ret, {'source': com1, 'target': com2, 'weight': new_weight});
});
return ret;
}
function partition_at_level(dendogram, level){
var partition = clone(dendogram[0]);
for(var i = 1; i < level + 1; i++ )
Object.keys(partition).forEach(function(key,j){
var node = key;
var com = partition[key];
partition[node] = dendogram[i][com];
});
return partition;
}
function generate_dendogram(graph, part_init){
if(graph.edges.length == 0){
var part = {};
graph.nodes.forEach(function(node,i){
part[node] = node;
});
return part;
}
var status = {};
init_status(original_graph, status, part_init);
var mod = __modularity(status);
var status_list = [];
__one_level(original_graph, status);
var new_mod = __modularity(status);
var partition = __renumber(status.nodes_to_com);
status_list.push(partition);
mod = new_mod;
var current_graph = induced_graph(partition, original_graph);
init_status(current_graph, status);
while (true){
__one_level(current_graph, status);
new_mod = __modularity(status);
if(new_mod - mod < __MIN)
break;
partition = __renumber(status.nodes_to_com);
status_list.push(partition);
mod = new_mod;
current_graph = induced_graph(partition, current_graph);
init_status(current_graph, status);
}
return status_list;
}
var core = function(){
var status = {};
var dendogram = generate_dendogram(original_graph, partition_init);
return partition_at_level(dendogram, dendogram.length - 1);
};
core.nodes = function(nds){
if(arguments.length > 0){
original_graph_nodes = nds;
}
return core;
};
core.edges = function(edgs){
if(typeof original_graph_nodes == 'undefined')
throw 'Please provide the graph nodes first!';
if(arguments.length > 0){
original_graph_edges = edgs;
var assoc_mat = make_assoc_mat(edgs);
original_graph = { 'nodes': original_graph_nodes,
'edges': original_graph_edges,
'_assoc_mat': assoc_mat };
}
return core;
};
core.partition_init = function(prttn){
if(arguments.length > 0){
partition_init = prttn;
}
return core;
};
return core;
}
})();