The Reingold-Tilford tree layout algorithm for HeuristicLab

[bburlacu]

I implemented the layout algorithm described in the paper of Buchheim, Jünger and Leipert, Drawing rooted trees in linear time [1], which is an improvement in terms of computational complexity of the Reingold-Tilford algorithm.

The resulting trees seem to be more compact and more balanced.

Example:

[1] ​http://dl.acm.org/citation.cfm?id=1133017

[bburlacu]

r9650: Created branch and committed first version of the implementation.

[gkronber]

I think this should be integrated into the trunk as soon as possible. Please accept the ticket, and merge to trunk when you feel the implementation is ready. Ideally, we can release this with the next milestone 3.3.9.

[gkronber]

Please don't show the root node if it has only one child (#2092).

[bburlacu]

r9852: Created new branch as the old one was crashing subversion:

• Restructured branch contents, created HeuristicLab.TreeLayout solution.
• Merged HeuristicLab.Encodings.SymbolicExpressionTreeEncoding and HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views from the trunk
• Renamed TreeLayout to ReingoldTilfordLayoutEngine and moved it to HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/LayoutEngines
• Added SymbolicExpressionTreeLatexFormatter and modified the SymbolicExpressionTreeChart to allow the export of tree in pgf/latex format (using the formatter and the layout engine).

[bburlacu]

r9853: Deleted old branch.

[bburlacu]

Example pdf document compiled from the exported pgf/tikz latex file.

[bburlacu]

r9854: Wrapped dialog creation for pgf/tikz export in an using statement.

[bburlacu]

r9969: Deleted folders that weren't properly added to the branch.

[bburlacu]

r9970: Refactored layout engine to be more generic. Svn-copied folders from trunk and readded layout files.

[bburlacu]

r9993: Improved tree aspect by calculating maximum visual node width per level.

[bburlacu]

r10434: Merged trunk changes.

[gkronber]

r10467: fixed PreBuildEvent.cmd to allow building

[gkronber]

r10468: fixed name for TreeLatexFormatter

[gkronber]

Review comments:

• TreeLatexFormatter only works the first time (switch to another formatter and back to the TreeLatexFormatter to produce an error message).
• interface ILayoutNode<T> seems to be very specific to the Reingold-Tilford tree layout algorithm (especially properties: Mod, Prelim, Change, Shift, Number, Level). The interface is probably not necessary.
• What is the difference between 'ancestor' and 'parent' (in ILayoutNode)?
• Code is very readable and nicely documented.

[bburlacu]

r10471: Thanks for the feedback:

• I removed the ILayoutNode Interfaces
• Fixed the error that was causing it to crash in the textual representation
• The ancestor is a node on the path between the root and the current node (from the paper), but in the algorithm it's assigned differently
• Parent is the immediate parent

I also increased the node label text size a bit and did some cosmetic improvements.

[gkronber]

Another thing that I forgot to mention is that 'Save image' does not work. For both formats (EMF and BMP) the exported image only contains the lines connecting nodes but not the nodes.

[bburlacu]

r10487: Fixed image save to file in the SymbolicExpressionTreeChart. Removed commented code from SymbolicExpressionTreeLayoutAdapter.

[gkronber]

Reviewed r10471 and r10487 and tested the functionality again. From my point of view this is ready for trunk integration and release.

[bburlacu]

r10496: Integrated the Reingold-Tilford layout into the trunk.

[bburlacu]

r10519: Removed the layout adapter and moved the functionality into the layout engine itself. Moved the layout engine to HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views. Improved layout scaling when the screen bounds are smaller than the layout bounds.

[bburlacu]

r10520:

• Got rid of layout adapters.

• Extracted the previous drawing code and made it into another layout engine called the BoxesLayoutEngine (because it divides the areas necessary for each subtree into boxes and recursively applies the layout).

• Simplified usage of layout engine so that most of the things are handled internally, and the user just has to provide some lambdas telling the engine how to navigate the original tree.

• Added context option in the SymbolicExpressionTreeChart to choose which layout engine to use for tree drawing.

• Moved the SymbolicExpressionTreeLatexFormatter to the HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Views assembly because it depends on the layout engine.

[bburlacu]

r10521: Fixed build error due to incomplete commit (previous commit).

[bburlacu]

r10531: SymbolicExpressionTreeChart: initialize layout when the tree node is changed, not when the tree draw method is called.

[bburlacu]

r10561: Updated the way the layout is used in the SymbolicExpressionTreeChart; updated simplifier view accordingly.

[bburlacu]

r10564: Forgot to commit changes to the InteractiveSymbolicDataAnalysisSolutionSimplifierView for repainting node impacts after the InteractiveSymbolicExpressionTreeChart gets repainted.

[mkommend]

r10565: Simplified the API of the tree layout engines.

[bburlacu]

There are a few minor glitches with the layout engine:

• the visual nodes are reused but the tooltip is not reset (resulting in duplicate lines in the tooltip text)

• the tree should not be updated if no nodes have been folded

• an exception should be thrown if the visual node content is null

[bburlacu]

r10799: Improved visual aspect of trees using the Boxes layout engine (decreased horizontal spacing to a minimum of 1px). Refactored some code in the InteractiveSymbolicDataAnalysisSolutionSimplifierView to throw an exception when the visual node content is null, and to only update the tree when necessary.

[bburlacu]

r10800: Fixed typo in BoxesLayoutEngine.cs

[mkommend]

r10862: Increased vertical and horizontal spacing for the boxes layout of symbolic expression tree charts.

[gkronber]

The "Export to Excel" functionality seems to be affected by the changes in this ticket. The image of the tree in the Excel file is incomplete and shows only the lines connecting nodes but not the nodes themselves. Please check and correct this.

[bburlacu]

r10885: Fixed incorrect call to DrawNode which caused problems with emf export.

[gkronber]

Excel export works beautifully now.

[gkronber]

Note, it is necessary to merge r10499 (from #2092) together with the changes in this ticket.

[gkronber]

r11065: minor changes to the code while reviewing / testing

[gkronber]

Tested the functionality and reviewed the code. This functionality is ready for release.

[gkronber]

r11120:

#2076,#2159, #2092 multi-ticket merge to stable:

• merged r10496,r10519,r10520,r10521,r10531,r10561,r10564,r10565,r10799,r10800,r10862,r10885,r11065 (#2076)
• merged r10499 (#2092)
• merged r10522,r10523,r10953,r10956 (#2159)