Skip to content

Instantly share code, notes, and snippets.

@caoyue caoyue/mptt.py
Created May 11, 2015

Embed
What would you like to do?
rebuild modified preorder tree
#-*- coding: utf-8 -*-
class Node(object):
def __init__(self, left, right):
super(Node, self).__init__()
self.left = left
self.right = right
self.depth = 1
self.name = "%s< >%s" % (self.left, self.right)
self.children = []
def to_JSON(self):
import json
return json.dumps(self, default=lambda o: o.__dict__,
sort_keys=False, indent=4)
@classmethod
def rebuild(cls, l):
l.sort(key=lambda x: x.left)
pi = [0]
for i, c in enumerate(l):
if c.left != 1:
p = l[i - 1]
if c.left == p.left + 1:
c.depth = p.depth + 1
if c.depth - 1 > len(pi):
pi.append(i - 1)
else:
pi[c.depth - 2] = i - 1
elif c.left > l[pi[p.depth - 2]].right:
c.depth = p.depth - (c.left - p.right - 1)
else:
c.depth = p.depth
l[pi[c.depth - 2]].children.append(c)
return l
@classmethod
def nprint(cls, n):
print "|----" * (n.depth - 1) + "Node: l:%s, r:%s, depth:%s" % (n.left, n.right, n.depth)
if n.children:
for x in n.children:
cls.nprint(x)
@classmethod
def visual(cls, json):
with open("tree.html", 'r+') as f:
s = f.read().replace("<<JSON_HERE>>", json)
f.seek(0)
f.write(s)
if __name__ == '__main__':
l = [
Node(1, 26),
Node(3, 6),
Node(2, 13),
Node(4, 5),
Node(7, 12),
Node(8, 9),
Node(10, 11),
Node(14, 15),
Node(19, 20),
Node(16, 25),
Node(17, 24),
Node(18, 21),
Node(22, 23)
]
Node.rebuild(l)
print "Tree:"
Node.nprint(l[0])
json = l[0].to_JSON()
print "Json:"
print json
Node.visual(json)
print ">> open tree.html to see the tree structre..."
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Test Tree</title>
<style>
.node {
cursor: pointer;
}
.node circle {
fill: #fff;
stroke: steelblue;
stroke-width: 3px;
}
.node text {
font: 12px sans-serif;
}
.link {
fill: none;
stroke: #ccc;
stroke-width: 2px;
}
</style>
</head>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>
var treeData =
[
<<JSON_HERE>>
];
// ************** Generate the tree diagram *****************
var margin = {
top: 20,
right: 120,
bottom: 20,
left: 120
},
width = 960 - margin.right - margin.left,
height = 500 - margin.top - margin.bottom;
var i = 0,
duration = 750,
root;
var tree = d3.layout.tree()
.size([height, width]);
var diagonal = d3.svg.diagonal()
.projection(function(d) {
return [d.y, d.x];
});
var svg = d3.select("body").append("svg")
.attr("width", width + margin.right + margin.left)
.attr("height", height + margin.top + margin.bottom)
.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
root = treeData[0];
root.x0 = height / 2;
root.y0 = 0;
update(root);
d3.select(self.frameElement).style("height", "500px");
function update(source) {
// Compute the new tree layout.
var nodes = tree.nodes(root).reverse(),
links = tree.links(nodes);
// Normalize for fixed-depth.
nodes.forEach(function(d) {
d.y = d.depth * 180;
});
// Update the nodes…
var node = svg.selectAll("g.node")
.data(nodes, function(d) {
return d.id || (d.id = ++i);
});
// Enter any new nodes at the parent's previous position.
var nodeEnter = node.enter().append("g")
.attr("class", "node")
.attr("transform", function(d) {
return "translate(" + source.y0 + "," + source.x0 + ")";
})
.on("click", click);
nodeEnter.append("circle")
.attr("r", 1e-6)
.style("fill", function(d) {
return d._children ? "lightsteelblue" : "#fff";
});
nodeEnter.append("text")
.attr("x", function(d) {
return d.children || d._children ? -13 : 13;
})
.attr("dy", ".35em")
.attr("text-anchor", function(d) {
return d.children || d._children ? "end" : "start";
})
.text(function(d) {
return d.name;
})
.style("fill-opacity", 1e-6);
// Transition nodes to their new position.
var nodeUpdate = node.transition()
.duration(duration)
.attr("transform", function(d) {
return "translate(" + d.y + "," + d.x + ")";
});
nodeUpdate.select("circle")
.attr("r", 10)
.style("fill", function(d) {
return d._children ? "lightsteelblue" : "#fff";
});
nodeUpdate.select("text")
.style("fill-opacity", 1);
// Transition exiting nodes to the parent's new position.
var nodeExit = node.exit().transition()
.duration(duration)
.attr("transform", function(d) {
return "translate(" + source.y + "," + source.x + ")";
})
.remove();
nodeExit.select("circle")
.attr("r", 1e-6);
nodeExit.select("text")
.style("fill-opacity", 1e-6);
// Update the links…
var link = svg.selectAll("path.link")
.data(links, function(d) {
return d.target.id;
});
// Enter any new links at the parent's previous position.
link.enter().insert("path", "g")
.attr("class", "link")
.attr("d", function(d) {
var o = {
x: source.x0,
y: source.y0
};
return diagonal({
source: o,
target: o
});
});
// Transition links to their new position.
link.transition()
.duration(duration)
.attr("d", diagonal);
// Transition exiting nodes to the parent's new position.
link.exit().transition()
.duration(duration)
.attr("d", function(d) {
var o = {
x: source.x,
y: source.y
};
return diagonal({
source: o,
target: o
});
})
.remove();
// Stash the old positions for transition.
nodes.forEach(function(d) {
d.x0 = d.x;
d.y0 = d.y;
});
}
// Toggle children on click.
function click(d) {
if (d.children) {
d._children = d.children;
d.children = null;
} else {
d.children = d._children;
d._children = null;
}
update(d);
}
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.