Skip to content

Instantly share code, notes, and snippets.

@designbyadrian

designbyadrian/.block

Last active September 12, 2016 11:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save designbyadrian/fbbd055ef9483851d73fe1202849cddf to your computer and use it in GitHub Desktop.
Save designbyadrian/fbbd055ef9483851d73fe1202849cddf to your computer and use it in GitHub Desktop.
Download ZIP
D3 v4 Force - Adding nodes incrementally
Raw
.block
license: gpl-3.0
Raw
README.md

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.

Raw
index.html
<!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>
Raw
script.js
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