tidy-trees

A library for making tidy drawings of trees.

Provides a reagent component which implements a O( n * depth ) algorithm for tree drawing inspired by Reingold and Tilford's Tidier Drawings of Trees and Bill Mill's survey of tree drawing algorithms Drawing Presentable Trees.

usage

If we want to draw some tree in an element with id target-el, we write: 

(ns example
  (:require [reagent.core :refer [render-component]
            [tidy-trees.reagent :refer [tidy-tree]))

  ...

  (render-component [tidy-tree tree opts] (. js/document (get-ElementById "#target-el"))

where opts is a map containing the following entries:

:branch?
function

When applied with a node, returns whether the node is a branch.

:children?
function

When applied with a node, returns the nodes children as a seq.

:label-branch
function

When applied with a branch node, returns a label for the branch node.

:label-term
function

When applied with a terminal node, returns a label for the terminal node.

:v-gap
number(px)

The minimum amount of space between levels.

:h-gap
number(px)

The amount of space between adjacent nodes on the same level.

:edges
keyword

Determines the way tree edges are draw.

binary search tree insertion

In the study of algorithms, we learn that binary search trees are an effective way to implement ordered sets. Given a balanced binary search tree of n elements, we can find any particular element in O(log(n)) time.

The adjacent drawing illustrates such a tree. The tree contains 15 elements and when we search for any element, we examine at most 4 nodes. Notice that every non-terminal node has two children, and all terminals occur on the same level.

However, our O(log(n)) bound does not hold for all binary search trees. Binary search trees are sensitive to insertion order. The list displayed above our example tree is the insertion order for the tree. Click the shuffle button to see what happens to our balanced tree whenever the insertion order changes. We find that perfectly balanced trees such as our first one are rare, and that the worst-case bound on finding a node is actually O(n).

hiccup-like trees

hiccup is a popular Clojure format for representing HTML trees where elements are vectors and maps are element attributes.

Below we have a simpler version of hiccup, where we omit attributes. Vectors represent non-terminal nodes, whose name is the first element, and children are the remaining elements. Everything else is a terminal node.

Try editing the tree below: