This instance doesn’t do much, but it does have a nice property: it’s only equal to itself

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com, or follow me on Twitter.

This is a very clever hack:

Graphviz assumes explicit identities for nodes, so what about when we want to represent a tree? We can’t simply use the identity of the node, because the same value at different positions within the tree must be treated as separate nodes. One possibility is to represent each node as a tuple of its value and its position in the tree, but this forces us to consider how to represent positions, which is neither obvious nor straightforward.

Luckily, there’s a better way.

(let [node->children (atom {})
      nodes (tree-seq
              (comp branch? second)
              (fn [x]
                (swap! node->children assoc x
                  (map vector
                    (repeatedly #(Object.))
                    (children (second x))))
                (@node->children x))
              [(Object.) root])]
  ...)

If we’re given the tree-seq parameters of root, branch? and children, we can simply walk the structure, and transform each node into a unique version of itself. Since tree-seq only visits each node once, we don’t need a reproducible unique value, we can simply create a tuple of the value and (Object.), which creates an instance of the base class for all Java objects. This instance doesn’t do much, but it does have a nice property: it’s only equal to itself. Thus, the tuple we create with this object is unique no matter how many nodes share the same value. By flattening the tree using tree-seq, we have a list of nodes, and a function that gives adjacent nodes via #(@node->children %).

Post external references

  1. 1
    http://ideolalia.com/2013/12/18/rhizome.html
Source