Uses breadth-first traversal to add nodes, one by one, to a force graph. Because it takes a while for the network to reach equilibrium, I stop the simulation prematurely after a few hundred milliseconds after every new node.
Last active
September 12, 2016 11:53
-
-
Save designbyadrian/fbbd055ef9483851d73fe1202849cddf to your computer and use it in GitHub Desktop.
D3 v4 Force - Adding nodes incrementally
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
license: gpl-3.0 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html lang="en"> | |
<head> | |
<meta charset="UTF-8"> | |
<style> | |
body { | |
font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; | |
color: #333; | |
margin: 0; | |
padding: 0; | |
} | |
</style> | |
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/4.2.2/d3.min.js"></script> | |
<script> | |
var data = { | |
"nodes": [{ | |
"id": 1, | |
"name": "Jack Hayes", | |
"colour": "#567e7b", | |
"links": [58, 21, 33] | |
}, { | |
"id": 2, | |
"name": "Amy Castillo", | |
"colour": "#85ed67", | |
"links": [8, 22, 16, 28, 29, 31] | |
}, { | |
"id": 3, | |
"name": "Kenneth Williams", | |
"colour": "#666b01", | |
"links": [36, 22, 54] | |
}, { | |
"id": 4, | |
"name": "Phillip Hicks", | |
"colour": "#49d159", | |
"links": [37, 30, 46] | |
}, { | |
"id": 5, | |
"name": "Ryan Ortiz", | |
"colour": "#47f1ee", | |
"links": [] | |
}, { | |
"id": 6, | |
"name": "Edward Moore", | |
"colour": "#05626d", | |
"links": [23] | |
}, { | |
"id": 7, | |
"name": "Frances Gomez", | |
"colour": "#8ee92f", | |
"links": [] | |
}, { | |
"id": 8, | |
"name": "Julia Adams", | |
"colour": "#73e14b", | |
"links": [2, 45, 27, 56] | |
}, { | |
"id": 9, | |
"name": "Martha Montgomery", | |
"colour": "#0b9b89", | |
"links": [12, 52] | |
}, { | |
"id": 10, | |
"name": "Michelle Warren", | |
"colour": "#67bccd", | |
"links": [49, 41] | |
}, { | |
"id": 11, | |
"name": "Jonathan Lopez", | |
"colour": "#3fd669", | |
"links": [46, 12, 50] | |
}, { | |
"id": 12, | |
"name": "Kevin Holmes", | |
"colour": "#eb1277", | |
"links": [9, 11, 26, 54] | |
}, { | |
"id": 13, | |
"name": "William Clark", | |
"colour": "#15a191", | |
"links": [] | |
}, { | |
"id": 14, | |
"name": "Fred Martinez", | |
"colour": "#8a2c1b", | |
"links": [30, 24, 44] | |
}, { | |
"id": 15, | |
"name": "Antonio Spencer", | |
"colour": "#0d1310", | |
"links": [23, 57] | |
}, { | |
"id": 16, | |
"name": "Donald Mccoy", | |
"colour": "#574b92", | |
"links": [2, 35, 25] | |
}, { | |
"id": 17, | |
"name": "Paul Romero", | |
"colour": "#010778", | |
"links": [58, 37] | |
}, { | |
"id": 18, | |
"name": "Helen Pierce", | |
"colour": "#7a99e6", | |
"links": [40, 19, 21] | |
}, { | |
"id": 19, | |
"name": "Brenda Ortiz", | |
"colour": "#5596e4", | |
"links": [18] | |
}, { | |
"id": 20, | |
"name": "Steve Green", | |
"colour": "#341162", | |
"links": [31, 35, 42] | |
}, { | |
"id": 21, | |
"name": "Ernest Howell", | |
"colour": "#e7272f", | |
"links": [1, 18] | |
}, { | |
"id": 22, | |
"name": "Patricia Rodriguez", | |
"colour": "#9d66f9", | |
"links": [2, 3, 43] | |
}, { | |
"id": 23, | |
"name": "Lori Turner", | |
"colour": "#2cd25d", | |
"links": [6, 15] | |
}, { | |
"id": 24, | |
"name": "Jeremy Woods", | |
"colour": "#9bdc2f", | |
"links": [14] | |
}, { | |
"id": 25, | |
"name": "Wayne Spencer", | |
"colour": "#c13fce", | |
"links": [16, 29] | |
}, { | |
"id": 26, | |
"name": "Maria Carpenter", | |
"colour": "#44e028", | |
"links": [12, 59] | |
}, { | |
"id": 27, | |
"name": "Janet Romero", | |
"colour": "#7334ad", | |
"links": [8] | |
}, { | |
"id": 28, | |
"name": "Donna Simmons", | |
"colour": "#8f6454", | |
"links": [2] | |
}, { | |
"id": 29, | |
"name": "Eugene Robinson", | |
"colour": "#0a2d04", | |
"links": [2, 25] | |
}, { | |
"id": 30, | |
"name": "Nancy Carter", | |
"colour": "#ff66e5", | |
"links": [14, 4, 59, 53] | |
}, { | |
"id": 31, | |
"name": "Martin Ellis", | |
"colour": "#90beb1", | |
"links": [20, 2] | |
}, { | |
"id": 32, | |
"name": "Bruce Wright", | |
"colour": "#c40c4d", | |
"links": [55, 45] | |
}, { | |
"id": 33, | |
"name": "Juan Bailey", | |
"colour": "#24208e", | |
"links": [1, 51] | |
}, { | |
"id": 34, | |
"name": "Jeremy Hunter", | |
"colour": "#46bc6e", | |
"links": [55] | |
}, { | |
"id": 35, | |
"name": "Janet Ford", | |
"colour": "#4ed90c", | |
"links": [16, 20] | |
}, { | |
"id": 36, | |
"name": "Alice Mason", | |
"colour": "#bbecab", | |
"links": [3, 57] | |
}, { | |
"id": 37, | |
"name": "Earl Richards", | |
"colour": "#695bfb", | |
"links": [4, 17, 38, 55] | |
}, { | |
"id": 38, | |
"name": "Harold Weaver", | |
"colour": "#964fa5", | |
"links": [37] | |
}, { | |
"id": 39, | |
"name": "Nicholas Bowman", | |
"colour": "#a8b665", | |
"links": [40] | |
}, { | |
"id": 40, | |
"name": "Shawn Jackson", | |
"colour": "#881d2d", | |
"links": [18, 39, 53] | |
}, { | |
"id": 41, | |
"name": "Donna Brooks", | |
"colour": "#844394", | |
"links": [10] | |
}, { | |
"id": 42, | |
"name": "Thomas Riley", | |
"colour": "#903676", | |
"links": [20] | |
}, { | |
"id": 43, | |
"name": "Judith Reed", | |
"colour": "#9aad6a", | |
"links": [22, 47, 49] | |
}, { | |
"id": 44, | |
"name": "Bonnie Sullivan", | |
"colour": "#e58ca5", | |
"links": [14] | |
}, { | |
"id": 45, | |
"name": "Jesse Smith", | |
"colour": "#bb88e3", | |
"links": [8, 32] | |
}, { | |
"id": 46, | |
"name": "Frank Schmidt", | |
"colour": "#e89edb", | |
"links": [11, 4] | |
}, { | |
"id": 47, | |
"name": "Teresa Nelson", | |
"colour": "#1e92b7", | |
"links": [43] | |
}, { | |
"id": 48, | |
"name": "Beverly Burke", | |
"colour": "#876792", | |
"links": [] | |
}, { | |
"id": 49, | |
"name": "Martin Bowman", | |
"colour": "#4eea06", | |
"links": [10, 43] | |
}, { | |
"id": 50, | |
"name": "Ann Bowman", | |
"colour": "#1d3199", | |
"links": [11] | |
}, { | |
"id": 51, | |
"name": "Sharon Wheeler", | |
"colour": "#2321d6", | |
"links": [33] | |
}, { | |
"id": 52, | |
"name": "Heather Coleman", | |
"colour": "#960f50", | |
"links": [9] | |
}, { | |
"id": 53, | |
"name": "Linda Peters", | |
"colour": "#c11be7", | |
"links": [40, 30] | |
}, { | |
"id": 54, | |
"name": "Joseph Williams", | |
"colour": "#1dbb7f", | |
"links": [3, 12] | |
}, { | |
"id": 55, | |
"name": "Dorothy Peters", | |
"colour": "#32d600", | |
"links": [32, 34, 37] | |
}, { | |
"id": 56, | |
"name": "Christopher Hughes", | |
"colour": "#c8ff65", | |
"links": [8] | |
}, | |
{ | |
"id": 57, | |
"name": "Gerald Hernandez", | |
"colour": "#68da74", | |
"links": [36, 15] | |
}, | |
{ | |
"id": 58, | |
"name": "Joshua Ruiz", | |
"colour": "#e022ce", | |
"links": [1, 17] | |
}, { | |
"id": 59, | |
"name": "Carlos Johnson", | |
"colour": "#ff206d", | |
"links": [30, 26] | |
}] | |
}; | |
</script> | |
</head> | |
<body> | |
<canvas id="network" width="960" height="540"></canvas> | |
<script src="script.js"></script> | |
</body> | |
</html> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var network = { | |
width: 960, | |
height: 540, | |
graph: { | |
nodes: [], | |
links: [] | |
}, | |
lines: { | |
stroke: { | |
color: '#ccc', | |
thickness: 2 | |
}, | |
}, | |
nodes: { | |
stroke: { | |
color: '#fff', | |
thickness: 4 | |
}, | |
sizeRange: [16,64] | |
}, | |
setup: function(){ | |
/* For large networks (>1000) rendering an SVG would be too heavy for mobile devices */ | |
this.canvas = document.getElementById('network'); | |
this.context = this.canvas.getContext('2d'); | |
/* D3 part setup */ | |
let manyBody = d3.forceManyBody() | |
.strength((d)=>d.force) | |
.distanceMax(this.width/2) | |
forceCollide = d3.forceCollide() | |
.radius((d)=>d.collisionRadius) | |
.iterations(2) | |
forceCenter = d3.forceCenter(); | |
this.simulation = d3.forceSimulation() | |
.stop() // we want to control the runs | |
.force("link",d3.forceLink().id((d)=>d.id)) | |
.force("change",manyBody) | |
.force("center",forceCenter) | |
.force("collide",forceCollide) | |
.on("tick",()=>{ | |
this.tick(); | |
}); | |
this.getData(data).then((nodes)=>{ | |
this.drawTree(nodes); | |
}); | |
}, | |
/* Insert async data request of choice here. | |
Test data is found in the HTML file */ | |
getData: (data)=>{ | |
return new Promise((resolve,reject) => { | |
/* For BFS we want to start with the node with the most | |
children first. */ | |
data.nodes.sort((a,b)=>{ | |
if(a.links.length>b.links.length) { | |
return 1; | |
} | |
if(a.links.length<b.links.length) { | |
return -1; | |
} | |
return 0; | |
}); | |
resolve(data.nodes); | |
}); | |
}, | |
/* We draw nodes as we discover them in a Breadth-First Search fashion. | |
Of course, a force graph isn't necessarily shaped like a tree, | |
but we do the same for the sake of more fun visualisation and a slightly more efficient program */ | |
drawTree: function(nodes){ | |
let stack = [], | |
drawNodes = (waitUntilDone)=> { | |
return new Promise((resolve,reject)=>{ | |
/* It takes a while for the graph to reach equilibrium, | |
so we want to cut this sort until the very last node */ | |
if(waitUntilDone) { | |
this.simulation.on("end",()=>{ | |
resolve(); | |
}); | |
} else { | |
setTimeout(()=>{ | |
this.simulation.stop(); | |
resolve(); | |
},600); | |
} | |
this.plotData(); | |
}); | |
}, | |
/* Count links already in graph for each node */ | |
updateConnections = ()=> { | |
this.graph.nodes.forEach((node,index)=>{ | |
let connectedIds = [], | |
numConnections = this.graph.links.filter((link)=>{ | |
let hasConnection = false; | |
if(link.source.id == node.id && connectedIds.indexOf(link.target.id)<0) { | |
connectedIds.push(link.target.id); | |
hasConnection = true; | |
} | |
if(link.target.id == node.id && connectedIds.indexOf(link.source.id)<0) { | |
connectedIds.push(link.source.id); | |
hasConnection = true; | |
} | |
return hasConnection; | |
}); | |
node.connections = numConnections.length; | |
}); | |
}, | |
findNewLinks = (node)=> { | |
let newLinks = []; | |
if(!node.connections) { | |
node.connections = 0; // can't add 1 to null | |
} | |
node.links.forEach((link)=>{ | |
if(this.findNodeInGraph(link)<0) { | |
/* New node! */ | |
newLinks.push(link); | |
} else if(this.findLinkInGraph(link,node.id)<0) { | |
/* Not new node, but don't have the link yet! */ | |
this.graph.links.push({source:node.id,target:link}); | |
} | |
}); | |
/* Turn list of IDs to real node data */ | |
let neighbours = newLinks.filter((link)=>{ | |
return this.getNode(link,nodes); | |
}).map((neighbourId)=>{ | |
return this.getNode(neighbourId,nodes); | |
}); | |
/* We didn't discover any new nodes, so we'll add the next unvisisted node to the stack */ | |
if(neighbours.length<1) { | |
let newItem = nodes.pop(); | |
if(newItem) { | |
stack.push(newItem); | |
} | |
/* Add the new newighbour nodes to stack */ | |
} else { | |
stack.push(...neighbours); | |
} | |
}, | |
nextNode = ()=> { | |
if(stack.length>0) { | |
let node = stack.shift(), | |
existinNodeIndex = this.findNodeInGraph(node.id); | |
/* Node doesn't exist in graph... add it then! */ | |
if(existinNodeIndex<0) { | |
findNewLinks(node); | |
updateConnections(); | |
this.graph.nodes.push(node); | |
drawNodes().then(()=>{ | |
nextNode(); | |
}); | |
/* Node exists, buy its connections might not! */ | |
} else { | |
findNewLinks(node); | |
updateConnections(); | |
nextNode(); | |
} | |
} else { | |
console.info("Graph done! :D"); | |
drawNodes(true); | |
} | |
}; | |
/* Start with last node in list. We know it's ordered to have the highest number of neighbours */ | |
stack.push(nodes.pop()); | |
nextNode(); | |
}, | |
/* This is where we set up fun data for D3 */ | |
plotData: function(){ | |
let countExtent = d3.extent(this.graph.nodes,(d)=>{return d.connections?d.connections:1}), | |
radiusScale = d3.scalePow().exponent(2).domain(countExtent).range(this.nodes.sizeRange), | |
forceScale = d3.scalePow().exponent(2).domain(countExtent).range([-50,0]); | |
forceScale.clamp(true); | |
//radiusScale.clamp(true); leave this on if you feel D3 takes too many liberties. I believe in freedom! | |
this.graph.nodes.forEach((node)=>{ | |
/* The more connections, the larger the node */ | |
node.r = radiusScale(node.connections); | |
/* Make sure no node goes too close - also uses the minimum node size as margin */ | |
node.collisionRadius = node.r * 1.2; | |
/* Keep weaker nodes a further away */ | |
node.force = forceScale(node.connections); | |
}); | |
/* Hey D3! Catch! */ | |
this.simulation | |
.nodes(this.graph.nodes); | |
this.simulation.force("link") | |
.links(this.graph.links); | |
this.simulation.alpha(0.2).restart(); | |
}, | |
/* Draw onto canvas, or SVG, or whatever else */ | |
tick: function(){ | |
this.context.clearRect(0,0,this.width,this.height); | |
this.context.save(); | |
this.context.translate(this.width/2,this.height/2); | |
this.context.beginPath(); | |
this.graph.links.forEach((link)=>{ | |
this.context.moveTo(link.source.x,link.source.y); | |
this.context.lineTo(link.target.x,link.target.y); | |
}); | |
this.context.strokeStyle = this.lines.stroke.color; | |
this.context.lineWidth = this.lines.stroke.thickness; | |
this.context.stroke(); | |
this.graph.nodes.forEach((node)=>{ | |
this.context.beginPath(); | |
this.context.arc(node.x, node.y, node.r, 0, 2 * Math.PI); | |
this.context.fillStyle = node.colour; | |
this.context.strokeStyle = this.nodes.stroke.color; | |
this.context.lineWidth = this.nodes.stroke.thickness; | |
this.context.fill(); | |
this.context.stroke(); | |
}); | |
this.context.restore(); | |
}, | |
findNodeInGraph: function(id) { | |
var result = -1; | |
this.graph.nodes.forEach((node,index)=>{ | |
if(node.id==id) { | |
result = index; | |
return false; | |
} | |
}); | |
return result; | |
}, | |
getNode: function(id,nodes) { | |
result = null; | |
nodes.forEach((node,index)=>{ | |
if(node.id == id) { | |
result = node; | |
return false; | |
} | |
}); | |
return result; | |
}, | |
findLinkInGraph: function(source,target) { | |
var result = -1; | |
this.graph.links.forEach((link,index)=>{ | |
if( | |
link.source.id == source && link.target.id == target || | |
link.source.id == target && link.target.id == source | |
) { | |
result = index; | |
return false; | |
} | |
}); | |
return result; | |
} | |
}; | |
network.setup(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment