Opened 4 years ago

Closed 3 years ago

#2076 closed enhancement (done)

The Reingold-Tilford tree layout algorithm for HeuristicLab

Reported by: bburlacu Owned by: gkronber
Priority: medium Milestone: HeuristicLab 3.3.10
Component: Encodings.SymbolicExpressionTreeEncoding.Views Version: 3.3.9
Keywords: Cc:

Description

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: http://i.imgur.com/htGwxGS.png

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

Attachments (1)

layout.pdf (20.2 KB) - added by bburlacu 4 years ago.
Example pdf document compiled from the exported pgf/tikz latex file.

Download all attachments as: .zip

Change History (47)

comment:1 Changed 4 years ago by bburlacu

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

comment:2 Changed 4 years ago by 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.

comment:3 Changed 4 years ago by bburlacu

  • Status changed from new to accepted

comment:4 Changed 4 years ago by gkronber

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

comment:5 Changed 4 years ago by 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).

comment:6 Changed 4 years ago by bburlacu

r9853: Deleted old branch.

Changed 4 years ago by bburlacu

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

comment:7 Changed 4 years ago by bburlacu

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.9
  • Owner changed from bburlacu to mkommend
  • Status changed from accepted to reviewing

comment:8 Changed 4 years ago by bburlacu

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

comment:9 Changed 4 years ago by bburlacu

  • Owner changed from mkommend to bburlacu
  • Status changed from reviewing to assigned

comment:10 Changed 4 years ago by ascheibe

  • Milestone changed from HeuristicLab 3.3.9 to HeuristicLab 3.3.10

comment:11 Changed 4 years ago by bburlacu

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

comment:12 Changed 4 years ago by bburlacu

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

comment:13 Changed 4 years ago by bburlacu

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

comment:14 Changed 4 years ago by bburlacu

  • Owner changed from bburlacu to gkronber
  • Status changed from assigned to reviewing

comment:15 Changed 4 years ago by bburlacu

r10434: Merged trunk changes.

comment:16 Changed 4 years ago by gkronber

r10467: fixed PreBuildEvent.cmd to allow building

comment:17 Changed 4 years ago by gkronber

r10468: fixed name for TreeLatexFormatter

comment:18 follow-up: Changed 4 years ago by gkronber

  • Owner changed from gkronber to bburlacu
  • Status changed from reviewing to assigned

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.

comment:19 in reply to: ↑ 18 Changed 4 years ago by 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.

comment:20 Changed 4 years ago by 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.

comment:21 Changed 4 years ago by bburlacu

  • Owner changed from bburlacu to gkronber
  • Status changed from assigned to reviewing

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

comment:22 Changed 4 years ago by gkronber

  • Owner changed from gkronber to bburlacu
  • Status changed from reviewing to assigned

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

comment:23 Changed 4 years ago by bburlacu

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

comment:24 Changed 4 years ago by 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.

comment:25 Changed 4 years ago by 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.
Last edited 4 years ago by bburlacu (previous) (diff)

comment:26 Changed 4 years ago by bburlacu

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

comment:27 Changed 4 years ago by bburlacu

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

comment:28 Changed 4 years ago by bburlacu

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

comment:29 Changed 4 years ago by bburlacu

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

comment:30 Changed 4 years ago by mkommend

r10565: Simplified the API of the tree layout engines.

comment:31 Changed 4 years ago by mkommend

  • Status changed from assigned to reviewing

comment:32 Changed 4 years ago by mkommend

  • Cc michael.kommenda@heuristiclab.com gabriel.kronberger@heuristiclab.com removed
  • Version changed from branch to 3.3.9

comment:33 Changed 3 years ago by mkommend

  • Owner changed from bburlacu to gkronber

comment:34 Changed 3 years ago by bburlacu

  • Owner changed from gkronber to bburlacu
  • Status changed from reviewing to assigned

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

comment:35 Changed 3 years ago by 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.

comment:36 Changed 3 years ago by bburlacu

r10800: Fixed typo in BoxesLayoutEngine.cs

comment:37 Changed 3 years ago by mkommend

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

comment:38 Changed 3 years ago by 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.

comment:39 Changed 3 years ago by bburlacu

  • Status changed from assigned to accepted

comment:40 Changed 3 years ago by bburlacu

  • Owner changed from bburlacu to gkronber
  • Status changed from accepted to reviewing

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

comment:41 Changed 3 years ago by gkronber

Excel export works beautifully now.

comment:42 Changed 3 years ago by gkronber

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

comment:43 Changed 3 years ago by gkronber

r11065: minor changes to the code while reviewing / testing

comment:44 Changed 3 years ago by gkronber

  • Status changed from reviewing to readytorelease

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

comment:46 Changed 3 years ago by gkronber

  • Resolution set to done
  • Status changed from readytorelease to closed
Note: See TracTickets for help on using tickets.