Ordered trees

[stevenbird]

Add a layout option for ordered trees, cf:
https://github.com/mbostock/d3/wiki/Tree-Layout#tree

[jarredgallina]

Hey @Muon, in order to use the tree layout our data needs to be formatted hierarchically. Does Edgy use flat formatting? That seems to be the case. This article suggests a method to convert the data, under the heading "Generating a tree diagram from ‘flat’ data". I've tried implementing this as part of redrawGraph() but had no luck, and thought I'd better ask for help. Is this where you'd do the conversion?

[Muon]

Yeah, we don't do anything special. Yes, I'd put it in redrawGraph(). You should be able to do it by specifying layout.children(function(d) { return /* child node __d3datum__s */ } when layout is a tree layout, and possibly calling layout.start() after that.

EDIT: no, this won't work. JSNetworkX's renderer expects the usual d3.force API, so it will pass in a list of nodes instead of the root node to layout.nodes(). I don't think this is going to be possible without a serious overhaul of its renderer.

EDIT 2: There Is Another Way. Write your own d3.force-compatible wrapper over d3.tree.

[stevenbird]

Once we have this it would be nice to illustrate using linguistic trees.

[cyderize]

Unfortunately, implementing this would require making changes to JSNetworkX, as the type of data d3.layout.tree works with is different from WebCOLA and d3.layout.force - it requires different function calls to initiate because it requires a root node and each node must have parent and children properties, whereas other layouts only require us to specify an array of nodes and an array of edges.

JSNetworkX does initialization itself and provides the layout with nodes and edges, which are not what the tree layout expects.

I'm not sure if it's worth making more of our own changes to JSNetworkX in order to get this to work.

[stevenbird]

@tgdwyer do you have any advice about rendering ordered trees?

[cyderize]

The issue I've come across with this is that using d3.layout.tree would require us to maintain an additional representation of a graph, as it is not natively compatible with the data structure JSNetworkX uses. It also requires somewhat different initialisation, so unlike the two current layout algorithms, which use identical interfaces, the ordered tree layout would need special treatment.

The ordered tree layout needs a root node (which would need to be specified by the user for undirected graphs as any node could be considered the root), and each node would need to know its children. We could generate the required data structure (we'd have to get the root node from the user and ensure the graph is acyclic) to use the tree layout.

Then if the graph were to change, we could regenerate the data structure to keep things synchronised and if the graph were to become cyclic, or the root deleted, then we could fall back to the previous layout algorithm.

This is certainly doable - I'm not sure about performance implications of keeping a secondary graph data structure synchronised, but I don't imagine it'd be too bad. It might require a bit of bug testing to ensure that it all works properly.

[stevenbird]

There are some more options to consider:

1. Create a new type of graph. Just as we have graph and digraph we would also have tree. There would be a new tree block which took a (singleton or list) of (labels and subtrees). There would be special purpose blocks like depth. We could convert to and from trees. Etc.

2. Create another set of example blocks. Just as we have the LinkedList example, we could also have a Tree example. The tree API would be implemented in Edgy.

3. Create a new class of blocks for layout. These blocks implement various layout algorithms, and set the absolute x and y values of nodes. They would need to be run after any change to a graph. A tree layout algorithm could be one such block.