Skip to content

Instantly share code, notes, and snippets.

@behrangsa

behrangsa/Node.java

Last active October 7, 2023 06:25
Show Gist options
  • Save behrangsa/fa370c108ef862b310a3dd0f03ae6038 to your computer and use it in GitHub Desktop.
Save behrangsa/fa370c108ef862b310a3dd0f03ae6038 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
illustration.html
<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport"
content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
</head>
<body>
<svg viewBox="0 0 640 480" width="640" height="480">
<defs>
<style>
.node {
fill: hsl(0, 0%, 100%);
stroke: black;
stroke-width: 1px;
}
.stroke {
stroke: hsl(0, 0%, 67%);
stroke-width: 1px;
}
.dotted-stroke {
stroke: hsla(0, 0%, 67%, 0.5);
stroke-width: 1px;
stroke-dasharray: 5 1;
}
.node2 {
fill: hsl(0, 0%, 100%);
stroke: hsl(219, 79%, 66%);
stroke-width: 1px;
}
.stroke2 {
stroke: hsl(219, 79%, 76%);
stroke-width: 1px;
}
.dotted-stroke2 {
stroke: hsla(219, 79%, 76%, 0.5);
stroke-width: 1px;
stroke-dasharray: 5 1;
}
</style>
</defs>
<!-- translate(270 0) -->
<g id="graph1" transform="translate(0 0)">
<rect width="170" height="340" fill="hsl(17, 100%, 92%, 0.5)" stroke="black"/>
<!-- transform="translate(10 0)" -->
<g>
<!-- transform="translate(10 10)" -->
<g id="subgraph1-1" transform="translate(0 10)">
<g transform="translate(50 0)">
<rect class="node" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">O</text>
</g>
<g transform="translate(10 100)">
<rect class="node" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">E</text>
</g>
<g transform="translate(80 100)">
<rect class="node" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">F</text>
</g>
<line x1="60" y1="20" x2="20" y2="100" class="stroke"/>
<line x1="60" y1="20" x2="90" y2="100" class="stroke"/>
<line x1="30" y1="110" x2="80" y2="110" class="dotted-stroke"/>
</g>
<g id="subgraph1-2" transform="translate(10 210)">
<g transform="translate(30 0)">
<rect class="node" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">A</text>
</g>
<g transform="translate(90 0)">
<rect class="node" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">D</text>
</g>
<line x1="70" y1="-80" x2="40" y2="0" class="stroke"/>
<line x1="70" y1="-80" x2="100" y2="0" class="stroke"/>
<line x1="50" y1="10" x2="90" y2="10" class="dotted-stroke"/>
</g>
<g id="subgraph1-3" transform="translate(10 310)">
<g transform="translate(60 0)">
<rect class="node" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">B</text>
</g>
<g transform="translate(120 0)">
<rect class="node" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">C</text>
</g>
<line x1="100" y1="-80" x2="70" y2="0" class="stroke"/>
<line x1="100" y1="-80" x2="130" y2="0" class="stroke"/>
<line x1="80" y1="10" x2="120" y2="10" class="dotted-stroke"/>
</g>
</g>
</g>
<g id="graph2" transform="translate(180 0)">
<rect width="280" height="340" fill="hsl(37, 100%, 92%, 0.5)" stroke="black"/>
<g transform="translate(10 0)">
<g id="subgraph1-1" transform="translate(30 10)">
<g transform="translate(60 100)">
<rect class="node2" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">N</text>
</g>
<g transform="translate(30 200)">
<rect class="node2" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">G</text>
</g>
<g transform="translate(90 200)">
<rect class="node2" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">M</text>
</g>
<line x1="70" y1="120" x2="40" y2="200" class="stroke2"/>
<line x1="70" y1="120" x2="100" y2="200" class="stroke2"/>
<line x1="50" y1="210" x2="90" y2="210" class="dotted-stroke2"/>
</g>
<g id="subgraph1-2" transform="translate(0 310)">
<g transform="translate(0 0)">
<rect class="node2" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">H</text>
</g>
<g transform="translate(60 0)">
<rect class="node2" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">I</text>
</g>
<g transform="translate(120 0)">
<rect class="node2" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">J</text>
</g>
<g transform="translate(180 0)">
<rect class="node2" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">K</text>
</g>
<g transform="translate(240 0)">
<rect class="node2" width="20" height="20"/>
<text x="10" y="15" text-anchor="middle" alignment-baseline="middle">L</text>
</g>
<line x1="130" y1="-80" x2="10" y2="0" class="stroke2"/>
<line x1="130" y1="-80" x2="70" y2="0" class="stroke2"/>
<line x1="130" y1="-80" x2="130" y2="0" class="stroke2"/>
<line x1="130" y1="-80" x2="190" y2="0" class="stroke2"/>
<line x1="130" y1="-80" x2="250" y2="0" class="stroke2"/>
</g>
</g>
</g>
</svg>
</body>
</html>
Raw
Node.java
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Node<T> {
private static final int DEFAULT_MODIFIER = 0;
private static final int DEFAULT_PRELIM = 0;
private Node<T> parent;
private List<Node<T>> children;
private T value;
private double x;
private double y;
private double width;
private double height;
private double prelim = DEFAULT_PRELIM;
private double modifier = DEFAULT_MODIFIER;
private Node<T> leftNeighbor;
public Node() {
this(null);
}
public Node(T value) {
this.value = value;
this.children = new ArrayList<>();
}
public Node<T> getParent() {
return parent;
}
public void setParent(Node<T> parent) {
this.parent = parent;
}
public List<Node<T>> getChildren() {
return children;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
public double getWidth() {
return width;
}
public void setWidth(double width) {
this.width = width;
}
public double getHeight() {
return height;
}
public void setHeight(double height) {
this.height = height;
}
public double getPrelim() {
return prelim;
}
public void setPrelim(double prelim) {
this.prelim = prelim;
}
public double getModifier() {
return modifier;
}
public void setModifier(double modifier) {
this.modifier = modifier;
}
public Node<T> getLeftNeighbor() {
return leftNeighbor;
}
public void setLeftNeighbor(Node<T> leftNeighbor) {
this.leftNeighbor = leftNeighbor;
}
public boolean isLeaf() {
return this.children.isEmpty();
}
public boolean hasChildren() {
return !getChildren().isEmpty();
}
public int getLevel() {
int level = 0;
Node<T> node = this;
while (node.getParent() != null) {
level += 1;
node = node.getParent();
}
return level;
}
public Node<T> getLeftSibling() {
if (parent == null) {
return null;
}
List<Node<T>> siblings = parent.getChildren();
int nodeIndex = siblings.indexOf(this);
if (nodeIndex == 0) {
return null;
}
return siblings.get(nodeIndex - 1);
}
public boolean hasLeftSibling() {
return getLeftSibling() != null;
}
public Node<T> getRightSibling() {
if (parent == null) {
return null;
}
List<Node<T>> siblings = parent.getChildren();
int nodeIndex = siblings.indexOf(this);
if (nodeIndex == siblings.size() - 1) {
return null;
}
return siblings.get(nodeIndex + 1);
}
public boolean hasRightSibling() {
return getRightSibling() != null;
}
public Node<T> getLeftChild() {
if (children.isEmpty()) {
return null;
}
return children.getFirst();
}
public Node<T> getRightChild() {
if (children.isEmpty()) {
return null;
}
return children.getLast();
}
public Node<T> getLeftmost(int targetLevel) {
targetLevel = targetLevel == -1 ? Integer.MAX_VALUE : targetLevel;
if (targetLevel <= this.getLevel() && targetLevel != -1) {
throw new IllegalArgumentException("Parameter targetLevel must be greater than the current level");
}
Stack<Node<T>> visitNext = new Stack<>();
visitNext.push(this);
while (!visitNext.empty()) {
Node<T> head = visitNext.pop();
if (head.getLevel() == targetLevel) {
return head;
}
if (head.children != null) {
for (int i = 0; i < head.children.size(); i++) {
int index = head.children.size() - i - 1;
Node<T> child = head.children.get(index);
visitNext.push(child);
}
}
}
return null;
}
public void incrementPrelimBy(double delta) {
setPrelim(prelim + delta);
}
public void incrementModifierBy(double delta) {
setModifier(modifier + delta);
}
public int maxDepth() {
Node<T> tree = this;
if (tree.getChildren().isEmpty()) {
return 1;
}
return tree.getChildren()
.stream()
.mapToInt(Node::maxDepth)
.max()
.orElse(0) + 1;
}
@Override
public String toString() {
if (value == null) {
return "<null>";
}
return value.toString();
}
}
Raw
WalkerAlgorithm.java
public class WalkerAlgorithm<T> {
private static final long MAX_DEPTH = Long.MAX_VALUE;
/**
* During the operation of the algorithm, we walk the tree two times.
* <p>
* Whenever we visit a new node {@code N} at a level {@code L}, we store it in this map.
* <p>
* Then whenever we need to look up a node's neighboring node to the left, we can consult this map.
* <p>
* For example, consider the following tree:
* <pre>
* A
* ┌───┼───┐
* B C D
* │ │
* E F
* </pre>
* <p>
* As you can see, node {@code A} is at level 0, nodes {@code B}, {@code C}, {@code D} are at level 1, and nodes
* {@code E} and {@code F} are at level 2.
* <p>
* When we arrive at node {@code F}, we can consult to look up its left neighbor {@code E} using this table:
* <pre>{@code
* // leftNeighbor will resolve to node "E"
* var leftNeighbor = previousNodeAtLevel.get(2);
* }</pre>
* <p>
* Similarly, when we arrive at node {@code C}:
* <pre>{@code
* // leftNeighbor will resolve to node "B"
* var leftNeighbor = previousNodeAtLevel.get(1);
* }</pre>
*/
private Map<Integer, Node<T>> previousNodeAtLevel;
private double siblingSeparation;
private double subtreeSeparation;
private double levelSeparation;
private double xTopAdjustment;
private double yTopAdjustment;
public WalkerAlgorithm(double siblingSeparation, double subtreeSeparation, double xTopAdjustment, double yTopAdjustment, double levelSeparation) {
this.previousNodeAtLevel = new HashMap<>();
this.siblingSeparation = siblingSeparation;
this.subtreeSeparation = subtreeSeparation;
this.xTopAdjustment = xTopAdjustment;
this.yTopAdjustment = yTopAdjustment;
this.levelSeparation = levelSeparation;
}
public WalkerAlgorithm() {
this(0, 0, 0, 0, 0);
}
public boolean position(Node<T> node) {
if (node != null) {
previousNodeAtLevel.clear();
firstWalk(node, 0);
xTopAdjustment = node.getX() - node.getPrelim();
yTopAdjustment = node.getY();
return secondWalk(node, 0, 0);
} else
return true;
}
void firstWalk(Node<T> thisNode, int currentLevel) {
var leftNeighbor = getPreviousNodeAtLevel(currentLevel);
thisNode.setLeftNeighbor(leftNeighbor);
setPreviousNodeAtLevel(currentLevel, thisNode);
thisNode.getChildren().forEach(child -> {
firstWalk(child, currentLevel + 1);
});
if (thisNode.isLeaf() || currentLevel == MAX_DEPTH) {
if (thisNode.hasLeftSibling()) {
thisNode.setPrelim(thisNode.getLeftSibling().getPrelim() + siblingSeparation + meanWidth(thisNode.getLeftSibling(), thisNode));
} else {
thisNode.setPrelim(0);
}
} else {
var midpoint = (thisNode.getLeftChild().getPrelim() + thisNode.getRightChild().getPrelim()) / 2;
if (thisNode.hasLeftSibling()) {
thisNode.setPrelim(thisNode.getLeftSibling().getPrelim() + siblingSeparation + meanWidth(thisNode.getLeftSibling(), thisNode));
thisNode.setModifier(thisNode.getPrelim() - midpoint);
apportion(thisNode, currentLevel);
} else {
thisNode.setPrelim(midpoint);
}
}
}
boolean secondWalk(Node<T> node, int level, double modSum) {
boolean result = true;
if (level <= MAX_DEPTH) {
double xTemp = xTopAdjustment + node.getPrelim() + modSum;
double yTemp = yTopAdjustment + (level * levelSeparation);
node.setX(xTemp);
node.setY(yTemp);
if (node.hasChildren()) {
result = secondWalk(
node.getLeftChild(),
level + 1,
modSum + node.getModifier()
);
if (result == true && node.hasRightSibling()) {
result = secondWalk(
node.getRightSibling(),
level + 1,
modSum
);
}
}
} else {
result = true;
}
return result;
}
void apportion(Node<T> treeNode, int baseLevel) {
var leftMost = treeNode.getLeftChild();
Node<T> leftNeighbor;
for (int level = baseLevel; level < treeNode.maxDepth(); level++) {
leftNeighbor = leftMost.getLeftNeighbor();
if (leftMost == null || leftNeighbor == null) {
return;
}
var leftModSum = 0.0;
var rightModSum = 0.0;
var ancestorLeftmost = leftMost;
var ancestorNeighbor = leftNeighbor;
while (ancestorLeftmost != treeNode) {
ancestorLeftmost = ancestorLeftmost.getParent();
ancestorNeighbor = ancestorNeighbor.getParent();
rightModSum += ancestorLeftmost.getModifier();
leftModSum += ancestorNeighbor.getModifier();
}
var moveDistance = (
leftNeighbor.getPrelim() +
leftModSum +
subtreeSeparation +
meanWidth(treeNode.getLeftSibling(), treeNode)
) - (leftMost.getPrelim() + rightModSum);
if (moveDistance > 0) {
var tempNode = treeNode;
var numLeftSiblings = 0;
while (tempNode != null && tempNode != ancestorNeighbor) {
numLeftSiblings += 1;
tempNode = tempNode.getLeftSibling();
}
if (tempNode != null) {
double portion = moveDistance / numLeftSiblings;
tempNode = treeNode;
while (tempNode != ancestorNeighbor) {
tempNode.incrementPrelimBy(moveDistance);
tempNode.incrementModifierBy(moveDistance);
moveDistance -= portion;
tempNode = tempNode.getLeftSibling();
}
} else {
return;
}
}
if (leftMost.getChildren().isEmpty()) {
leftMost = treeNode.getLeftmost(level + 2);
} else {
leftMost = leftMost.getLeftChild();
}
}
}
Node<T> getPreviousNodeAtLevel(int level) {
return previousNodeAtLevel.getOrDefault(level, null);
}
void setPreviousNodeAtLevel(int level, Node<T> node) {
previousNodeAtLevel.put(level, node);
}
Node<T> getLeftmostDescendant(Node<T> node, int level, int depth) {
if (level >= depth) {
return node;
}
if (node.isLeaf()) {
return null;
}
var rightmost = node.getLeftChild();
var leftmost = getLeftmostDescendant(rightmost, level + 1, depth);
while (leftmost == null && rightmost.hasRightSibling()) {
rightmost = rightmost.getRightSibling();
leftmost = getLeftmostDescendant(rightmost, level + 1, depth);
}
return leftmost;
}
double meanWidth(Node<T> n1, Node<T> n2) {
return (n1.getWidth() + n2.getWidth()) / 2.0;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment