Skip to content

Instantly share code, notes, and snippets.

@bobbydavid

bobbydavid/README.md

Created June 22, 2013 17:26
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save bobbydavid/5841683 to your computer and use it in GitHub Desktop.
Save bobbydavid/5841683 to your computer and use it in GitHub Desktop.
Download ZIP
DAG visualization
Raw
README.md

taken from https://github.com/bobbydavid/dag-visualization at 6/22/13.

The algorithm is:

Create a random DAG (topographically sorted).

Determine X-positions. For each node, find it's minimum X-position. Then, in reverse order, find the maximum X-position of nodes that can be moved forward.

Determine Y-positions. For each node, place it as near as possible to the mean Y-position of its parents. Give preference to placing nodes that have a single parent with a single child (a 1-1 relationship), so that these will always be shown in a straight line.

Raw
dag.js
// Generate DAG
var nodeCount = 20;
var svgWidth = 900, svgHeight = 800;
// The nodes are indexed by topological sort.
var nodes = d3.range(nodeCount).map(function(d) {
return { index: d, label: 'node ' + d };
});
var links = d3.range(nodeCount * nodeCount).map(function(i) {
return {
source: Math.floor(i / nodeCount),
target: i % nodeCount
};
}).filter(function(link) {
// Automatically reject edges that are against the topological sort.
// Otherwise, allow a random subset of possible edges.
return link.target > link.source && Math.random() > 0.9;
});
// Returns a helper function that takes two node indexes, and returns true if
// there is an edge from the 1st to the 2nd.
var isLinked = (function() {
var lookup = d3.range(nodeCount).map(function() {
return d3.range(nodeCount).map(function() { return false; });
});
links.forEach(function(link) {
lookup[link.source][link.target] = true;
});
return function(nodeIndex1, nodeIndex2) {
return lookup[nodeIndex1][nodeIndex2];
};
})();
// Matrix representation of the edges. The value is true when the edge exists.
// It should be a strictly upper triangular matrix.
var dagMatrixCells = d3.merge(d3.range(nodeCount).map(function(rowIndex) {
return d3.range(nodeCount).map(function(colIndex) {
return {
x: colIndex,
y: rowIndex,
value: isLinked(rowIndex, colIndex)
};
});
}));
//
// Create d3 Components.
//
// This is the d3 component that facilitates the force graph.
var force = d3.layout.force()
.nodes(nodes)
.links(links)
.size([svgWidth, svgHeight])
.linkDistance(30 * Math.sqrt(nodeCount))
.linkStrength(0.5)
.charge(-300);
// Run the simulation a few times to settle things down.
force.start();
for (var i = 0; i < 100; i++) { force.tick(); }
force.stop();
// Create a separate set of node objects for DAG, so the index values don't collide.
var dagNodes = d3.range(nodeCount).map(function(d) {
return { index: d, label: 'node ' + d };
});
var dagLinks = links.map(function(d) {
return { source: dagNodes[d.source.index], target: dagNodes[d.target.index] };
});
var dag = new dagLayout(dagNodes, dagLinks, svgWidth, svgHeight);
/*
var dag = d3.layout.dag()
.nodes(nodes)
.links(links)
.size([svgWidth, svgHeight])
.
*/
//
// Create SVG elements.
//
var svg = d3.select('#force')
.append('svg')
.attr({
width: svgWidth,
height: svgHeight,
xmlns: 'http://www.w3.org/2000/svg'
});
// This template defines an arrowhead, and is referred to by id.
svg.append('defs').append('marker')
.attr({
id: 'arrowhead',
refX: 13,
refY: 4,
markerUnits: 'strokeWidth',
markerWidth: 10,
markerHeight: 8,
orient: 'auto'
}).append('path').attr({
d: 'M 0 0 L 10 4 L 0 8 Z',
fill: 'red'
});
// Adjacency matrix.
var svgMatrix = svg.append('g').selectAll('.matrix')
.data(dagMatrixCells)
.enter().append('circle')
.attr('class', 'matrix')
.attr('cx', function(d) { return 10 * d.x + 5; })
.attr('cy', function(d) { return 10 * d.y + 5; })
.style('fill', function(d) { return d.y >= d.x ? 'lightgray' :
d.value ? 'red' : 'gray'; })
.attr('r', 4);
// Create the edges.
var svgEdges = svg.append('g').selectAll('.link')
.data(force.links())
.enter().append('line')
.attr('class', 'link')
.style('stroke', 'red')
.attr('marker-end', 'url(#arrowhead)');
// Create the Nodes, then select them all (to save work during each tick).
svg.append('g').selectAll('.node')
.data(force.nodes())
.enter().append('g')
.attr('class', 'node')
// .call(force.drag);
var svgNodes = svg.selectAll('.node')
svgNodes.append('circle')
.attr('r', 5);
svgNodes.append('text')
.attr('transform', 'translate(-6,20)')
.text(function(d) { return d.label; });
// Draw the DAG in its own SVG.
svg = d3.select('#dag')
.append('svg')
.attr({
width: svgWidth,
height: svgHeight,
xmlns: 'http://www.w3.org/2000/svg'
});
var svgDagEdges = svg.selectAll('.daglink')
.data(dagLinks)
.enter().append('line')
.attr('class', 'daglink')
.style('stroke', 'red')
.attr('marker-end', 'url(#arrowhead)')
.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; });
var svgDagNodes = svg.selectAll('.dagnode')
.data(dagNodes)
.enter().append('g')
.attr('class', 'dagnode')
.attr('transform', function(d) {
return 'translate(' + d.x + ',' + d.y + ')';
});
svgDagNodes.append('circle').attr('r', 5);
svgDagNodes.append('text')
.attr('transform', 'translate(-6,20)')
.text(function(d) { return d.label; });
// The tick function will update the force graph every tick.
function tick() {
svgEdges
.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; });
svgNodes
.attr('transform', function(d) {
return 'translate(' + d.x + ',' + d.y + ')';
});
}
// Everything is ready. Start the simulation!
force.start()
.on('tick', tick)
.tick().tick();
force.stop();
// Class for DAG layout.
function dagLayout(nodes, links, svgWidth, svgHeight) {
// For now, assume nodes are topologically sorted (they are).
// Create reference arrays to parents and children.
nodes.forEach(function(node) {
node.children = [];
node.parents = [];
});
links.forEach(function(link) {
var sourceNode = link.source
var targetNode = link.target;
sourceNode.children.push(targetNode);
targetNode.parents.push(sourceNode);
});
// Calculate X values in sorted order.
for (var i = 0; i < nodes.length; i++) {
var node = nodes[i];
// Determine the minimum X value.
node.x = d3.max(node.parents, function(node) { return node.x; }) + 1 || 0;
}
// Promote X-values in reverse node order.
for (var i = nodes.length - 1; i >= 0; i--) {
var node = nodes[i];
// If a node has children farther in the future, push it towards them.
var maxX = d3.min(node.children, function(node) { return node.x; }) - 1;
if (maxX) {
console.log('moving X ' + node.x + ' -> ' + maxX);
node.x = maxX;
}
node.x = maxX ? maxX : node.x;
}
nodes.sort(function(a, b) { return a.x - b.x; });
console.log('SORTED:');
console.log(nodes);
// Stateful function to remember which spots are "taken".
var nearestY = (function() {
var taken = {};
return function(x, y) {
taken[x] = taken[x] || {};
var oldY = y;
while (taken[x][y]) {
y += 1;
}
taken[x][y] = true;
console.log('nearestY(' + x + ',' + oldY + ') -> ' + y);
return y;
};
})();
var onlyChild = function(node) {
return node.parents.length == 1 && node.parents[0].children.length == 1;
};
var placementIndex = 0;
nodes.forEach(function(node) {
if (node.parents.length == 0) {
node.y = nearestY(node.x, 0);
node.label += ' -(' + placementIndex++ + ')';
console.log('Placed ' + node.label);
} else if (onlyChild(node)) {
// Skip. This node has already been placed.
return;
} else {
var avgY = Math.floor(d3.mean(node.parents, function(p) { return p.y; }));
node.y = nearestY(node.x, avgY);
node.label += ' M(' + placementIndex++ + ')';
console.log('Placed ' + node.label);
}
while (node.children.length == 1 && onlyChild(node.children[0])) {
var child = node.children[0];
child.y = nearestY(child.x, node.y);
node = child;
node.label += ' +(' + placementIndex++ + ')';
console.log('Placed ' + node.label);
}
});
nodes.forEach(function(node) {
node.x = node.x * 100 + 50;
node.y = node.y * 50 + 50;
})
}
Raw
index.html
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<style>
body { background-color: #f5f5f5;}
svg { background-color: #fff; border: 1px solid #eee; }
.svgHolder { margin: 20px; }
.daglink { fill: none; }
</style>
</head>
<body>
<h2>DAG as force graph</h2>
<div class='svgHolder' id="force"></div>
<div class='svgHolder' id="dag"></div>
<footer>Robert Martin</footer>
<script type="text/javascript" src="http://d3js.org/d3.v3.js"></script>
<script type="text/javascript" src="dag.js"></script>
</body>
<html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment