Public
Edited
Apr 4, 2023
{
let tree = [...test_data[0].nodes];
function layout(node, depth) {
// do left side lookup
if (node.left != undefined) {
layout(tree[node.left], depth + 1);
}
if (node.right != undefined) {
layout(tree[node.right], depth + 1);
}
// handle leafs
if (node.left == undefined && node.right == undefined) {
node.offset = 0;
return;
}
// do right side look up
// once here we either know that we have walked back up the recursive stack or we are in the leaf node
setInitialContour(node);
// set whole left subtree's left and right contours
//
let min_offset = findOffset(node.left, node.right);
setxvalues(node.right, min_offset);
updateContours(node.left, node.right);
}
function setInitialContour(node) {
// recall the right child can be part of the left contour if there's no left child
if (node.left == undefined) {
node.left_contour = node.right;
} else {
node.left_contour = node.left;
}
if (node.right == undefined) {
node.right_contour = node.left;
} else {
node.right_contour = node.right;
}
}
function findOffset(left, right) {
// alternative is that we perform the tree walk and the offset calc in the below while loop
// that's more like the paper's algorithm than the other one online
let left_offsets = [];
let right_offsets = [];
while (left != undefined && right != undefined) {
let lnode = tree[left];
left_offsets.push(lnode.offset);
// make sure that we follow the contour not just the set of children
left = lnode.right_contour;
let rnode = tree[right];
right_offsets.push(rnode.offset);
right = rnode.left_contour;
}
// now find the min offset required for the dif depths
let min_offset = 0;
for (let i = 0; i < left_offsets.length; i++) {
// think through the undefined case
let left_off_val = left_offsets[i];
let right_off_val = right_offsets[i];
let dist_between = left_off_val - right_off_val;
// if this is less than 0 thaat means the right node isn't overlapping on the left
// if it is 0 or greater we need to perform an offset
if (dist_between > -1) {
let temp_off;
// always need the +1 or they will be on top of each other
temp_off = dist_between + 1;
if (temp_off > min_offset) {
temp_off = min_offset;
}
}
}
return min_offset;
}
//
function setxvalues(node, offset) {
// this we do need to recurse over the entire tree because the x values of child nodes in a large right sub tree need to be updated multiple times
// handle the case where there is no right subtree so offset can stay 0
if (node != undefined) {
tree[node].offset = offset;
}
// should recurse over the other values, but will do this later since right now it's unclear whether that's truly performant or if instead we should freeze at the end to set the coordinates
}
function updateContours(left, right) {
// the purpose here is to make sure that as we go down through nodes in the right and left subtrees that we provide connections from the right contour into the left subtree which may be a different length than our original right subtree
while (left != undefined && right != undefined) {
let lnode = tree[left];
left = lnode.left_contour;
let rnode = tree[right];
right = rnode.right_contour;
if (left == undefined && right != undefined) {
// thread the left node's contour now,
lnode.left_contour = right;
left = right;
} else if (right == undefined && left != undefined) {
rnode.right_contour = left;
right = left;
}
}
}
// now loop over the offsets and
layout(tree[0], 0);
return tree;
}
test_data = [
{
nodes: [
{
id: 0,
left: 1,
right: 2
},
{
id: 1,
left: 3,
right: null
},
{
id: 2,
left: null,
right: null
},
{
id: 3,
left: 4,
right: null
},
{
id: 4,
left: null,
right: null
}
]
},
{
nodes: [
{
id: 0,
left: 1,
right: 3
},
{
id: 1,
left: 2,
right: null
},
{
id: 2,
left: null,
right: null
},
{
id: 3,
left: 4,
right: 6
},
{
id: 4,
left: 5,
right: null
},
{
id: 5,
left: null,
right: null
},
{
id: 6,
left: 7,
right: null
},
{
id: 7,
left: 8,
right: 9
},
{
id: 8,
left: null,
right: null
},
{
id: 9,
left: null,
right: null
}
]
},
{
nodes: [
{
id: 0,
left: 1,
right: 5
},
{
id: 1,
left: 2,
right: 3
},
{
id: 2,
left: null,
right: null
},
{
id: 3,
left: null,
right: null
},
{
id: 4,
left: null,
right: null
},
{
id: 5,
left: 4,
right: null
}
]
},
{
nodes: [
{
id: 0,
left: 1,
right: 2
},
{
id: 1,
left: 3,
right: 4
},
{
id: 2,
left: 5,
right: 6
},
{
id: 3,
left: null,
right: null
},
{
id: 4,
left: null,
right: null
},
{
id: 5,
left: 7,
right: 8
},
{
id: 6,
left: null,
right: null
},
{
id: 7,
left: null,
right: null
},
{
id: 8,
left: 9,
right: null
},
{
id: 9,
left: null,
right: null
}
]
},
{
nodes: [
{
id: 0,
left: 1,
right: 8
},
{
id: 1,
left: 2,
right: null
},
{
id: 2,
left: 10,
right: 3
},
{
id: 3,
left: null,
right: 4
},
{
id: 4,
left: null,
right: null
},
{
id: 5,
left: null,
right: null
},
{
id: 6,
left: 5,
right: null
},
{
id: 7,
left: 6,
right: 9
},
{
id: 8,
left: null,
right: 7
},
{
id: 9,
left: null,
right: null
},
{ id: 10, left: null, right: null }
]
}
]
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
