This example shows the combined use of Python and D3 for a randomized 2D space-filling algorithm and visualization. It uses D3's force-directed graph methods. For description of the example's motivations and space-filling algorithm see this blog post.
In [1]:
from IPython.core.display import HTML
from string import Template
import pandas as pd
import random, math
In [2]:
HTML('<script src="lib/d3/d3.min.js"></script>')
Out[2]:
In [3]:
def dotproduct(v1, v2):
return sum((a*b) for a, b in zip(v1, v2))
def vectorLength(v):
return math.sqrt(dotproduct(v, v))
def angleBtwnVectors(v1, v2):
dot = dotproduct(v1, v2)
det = v1[0]*v2[1] - v1[1]*v2[0]
r = math.atan2(det, dot)
return r * 180.0 / math.pi
def angleViolation(vectorList,maxAllowed):
violation = False
angleList = []
for i in range(0,len(vectorList)):
angleList.append( angleBtwnVectors([1,0],vectorList[i]) )
angleList.sort()
angleList.append(angleList[0] + 360.0)
for i in range(1,len(angleList)):
if abs(angleList[i] - angleList[i-1]) > maxAllowed:
violation = True
return violation
In [4]:
def addVertex(vertices):
r = len(vertices['x'])
vertices.ix[r,'x'] = 0
vertices.ix[r,'y'] = 0
return r
def locateVertex(p,r,vertices):
vertices.ix[r,'x'] = p[0]
vertices.ix[r,'y'] = p[1]
def addEdge(r1,r2,vertices):
for c in ['a1','a2','a3','a4','a5']:
if not vertices.ix[r1,c] > -1:
vertices.ix[r1,c] = r2
break
for c in ['a1','a2','a3','a4','a5']:
if not vertices.ix[r2,c] > -1:
vertices.ix[r2,c] = r1
break
In [5]:
config = {
'random_seed' : 17,
'xExt': [-0.1,1.1] ,
'yExt': [-0.1,1.1] ,
'densityX' : 40 ,
'densityY' : 20 ,
'prob_0' : 0.1 ,
'prob_3' : 0.075 ,
'num_mod_steps' : 10 ,
'mod_step_ratio' : 0.1
}
In [6]:
random.seed(config['random_seed'])
vertices = pd.DataFrame({'x':[],'y':[],
'a1':[],'a2':[],'a3':[],'a4':[],'a5':[],'a6':[] })
y = 0
densityX = config['densityX']
densityY = config['densityY']
nextLine = range(densityX)
for i in range(len(nextLine)):
r = addVertex(vertices)
for line in range(densityY):
currentLine = nextLine
nextLine = []
numPointsInLine = len(currentLine)
previousNone = False
for i in range(numPointsInLine):
p = [i/float(numPointsInLine-1),y]
locateVertex(p,currentLine[i],vertices)
if i > 0:
addEdge(currentLine[i-1],currentLine[i],vertices)
if line < densityY-1:
# push either 0, 1 or 3 new vertices
rnd = random.uniform(0,1)
valid = (not previousNone) and line > 0 and i > 0 and i < (numPointsInLine - 1)
if rnd < config['prob_0'] and valid:
# 0 vertices
previousNone = True
elif rnd < (config['prob_3'] + config['prob_0']) and line < densityY-2:
# 3 vertices
nv = []
for j in range(3):
if j == 0 and previousNone:
nv.append(len(vertices['x']) - 1)
else:
nv.append(addVertex(vertices))
nextLine.append(nv[j])
addEdge(currentLine[i],nv[0],vertices)
addEdge(currentLine[i],nv[2],vertices)
previousNone = False
else:
# 1 vertex
if previousNone:
nv = len(vertices['x']) - 1
else:
nv = addVertex(vertices)
nextLine.append(nv)
addEdge(currentLine[i],nv,vertices)
previousNone = False
y += 1.0 / float(densityY-1)
In [7]:
vertices.head(10)
Out[7]:
In [8]:
graph_config = pd.DataFrame(vertices).copy()
adjacencies = []
for i in range(len(graph_config['x'])):
ve = []
for j in range(1,7):
if graph_config.ix[i,'a'+str(j)] > -1:
ve.append( int(graph_config.ix[i,'a'+str(j)]) )
adjacencies.append(ve)
graph_config['adjacencies'] = adjacencies
graph_config['vertex'] = graph_config.index
graph_config = graph_config.drop(['a1','a2','a3','a4','a5','a6'],axis=1)
graph_config.head()
Out[8]:
In [9]:
graph_template = Template('''
<style>
.vertex {
fill: #777;
}
.edge {
stroke: #111;
stroke-opacity: 1;
stroke-width: 0.5;
}
.link {
stroke: #000;
stroke-width: 0.5px;
}
.node {
cursor: move;
fill: #ccc;
stroke: #000;
stroke-width: 0.25px;
}
.node.fixed {
fill: #f00;
}
</style>
<button id="restart" type="button">re-start animation</button>
<div>
<svg width="100%" height="352px" id="graph"></svg>
</div>
<script>
var width = 750;
var height = 350;
var svg = d3.select("#graph").append("g")
.attr("transform", "translate(" + 1 + "," + 1 + ")");
var draw_graph = function() {
svg.selectAll(".link").remove();
svg.selectAll(".node").remove();
var force = d3.layout.force()
.size([width, height])
.linkStrength(0.9)
.friction(0.9)
.linkDistance(1)
.charge(-1)
.gravity(0.007)
.theta(0.8)
.alpha(0.1)
.on("tick", tick);
var drag = force.drag()
.on("dragstart", dragstart);
var link = svg.selectAll(".link"),
node = svg.selectAll(".node");
var vertices = $vertices ;
graph = {'nodes': [], 'links': []}
vertices.forEach(function(v) {
var f = false;
if ( (v.x <= 0) || (v.x >= 1) || (v.y <= 0) || (v.y >= 0.999999999999999) ) {
f = true;
}
graph.nodes.push({'x': v.x * width, 'y': v.y * height, 'fixed': f })
var e = v.adjacencies;
for (var i=0; i<e.length; i++){
graph.links.push({'source': v.vertex, 'target': e[i] })
};
});
force
.nodes(graph.nodes)
.links(graph.links)
.start();
link = link.data(graph.links)
.enter().append("line")
.attr("class", "link");
node = node.data(graph.nodes)
.enter().append("circle")
.attr("class", "node")
.attr("r", 1.5)
.on("dblclick", dblclick)
.call(drag);
function tick() {
link.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; });
node.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; });
}
function dblclick(d) {
d3.select(this).classed("fixed", d.fixed = false);
}
function dragstart(d) {
d3.select(this).classed("fixed", d.fixed = true);
}
}
$( "#restart" ).on('click touchstart', function() {
draw_graph();
});
draw_graph();
</script>
''')
In [10]:
HTML(graph_template.safe_substitute({'vertices': graph_config.to_dict(orient='records')}))
Out[10]:
(Note that you can click on vertices and move them. The graph will update accordingly.)