Free cookie consent management tool by TermsFeed Policy Generator

Opened 11 years ago

Closed 10 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 11 years ago.
Example pdf document compiled from the exported pgf/tikz latex file.

Download all attachments as: .zip

Change History (47)

comment:1 Changed 11 years ago by bburlacu

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

comment:2 Changed 11 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 11 years ago by bburlacu

  • Status changed from new to accepted

comment:4 Changed 11 years ago by gkronber

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

comment:5 Changed 11 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 11 years ago by bburlacu

r9853: Deleted old branch.

Changed 11 years ago by bburlacu

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

comment:7 Changed 11 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 11 years ago by bburlacu

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

comment:9 Changed 10 years ago by bburlacu

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

comment:10 Changed 10 years ago by ascheibe

  • Milestone changed from HeuristicLab 3.3.9 to HeuristicLab 3.3.10

comment:11 Changed 10 years ago by bburlacu

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

comment:12 Changed 10 years ago by bburlacu

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

comment:13 Changed 10 years ago by bburlacu

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

comment:14 Changed 10 years ago by bburlacu

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

comment:15 Changed 10 years ago by bburlacu

r10434: Merged trunk changes.

comment:16 Changed 10 years ago by gkronber

r10467: fixed PreBuildEvent.cmd to allow building

comment:17 Changed 10 years ago by gkronber

r10468: fixed name for TreeLatexFormatter

comment:18 follow-up: Changed 10 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 10 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 10 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 10 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 10 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 10 years ago by bburlacu

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

comment:24 Changed 10 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 10 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 10 years ago by bburlacu (previous) (diff)

comment:26 Changed 10 years ago by bburlacu

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

comment:27 Changed 10 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 10 years ago by bburlacu

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

comment:29 Changed 10 years ago by bburlacu

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

comment:30 Changed 10 years ago by mkommend

r10565: Simplified the API of the tree layout engines.

comment:31 Changed 10 years ago by mkommend

  • Status changed from assigned to reviewing

comment:32 Changed 10 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 10 years ago by mkommend

  • Owner changed from bburlacu to gkronber

comment:34 Changed 10 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 10 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 10 years ago by bburlacu

r10800: Fixed typo in BoxesLayoutEngine.cs

comment:37 Changed 10 years ago by mkommend

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

comment:38 Changed 10 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 10 years ago by bburlacu

  • Status changed from assigned to accepted

comment:40 Changed 10 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 10 years ago by gkronber

Excel export works beautifully now.

comment:42 Changed 10 years ago by gkronber

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

comment:43 Changed 10 years ago by gkronber

r11065: minor changes to the code while reviewing / testing

comment:44 Changed 10 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 10 years ago by gkronber

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