Trees.hpp File Reference

Plans for drawing trees (especially search trees) More...

Go to the source code of this file.

Detailed Description

Plans for drawing trees (especially search trees)

Create milestones.
Investigate existing software
Reingold-Tilford algorithm outline
  • See the MSc thesis of Warren Bailey (supervisor OK).
  • Investigate colouring schemes (see discussion of OK with Mark Jones).
  • The nodes are labelled with numerical vectors, and also the edges.
  • Additionally we have also strings as labels, like branching variables (for the nodes) and branching literals (for the edges).
  • First we implement the algorithm at Maxima/Lisp level.
    1. See ComputerAlgebra/Trees/Lisp/plans/ReingoldTilford.hpp.
    2. Input is a tree, output is the same tree, but labelled with the coordinates.
    3. We have the basic form of the algorithm, just implementing directly the definitions (so very clear, but also very slow).
    4. And then we have the linear-time algorithm.
Four aesthetic criterions for Reingold-Tilford algorithm
  • The Reingold-Tilford algorithm realises four basic criterions for tree drawing. We need to discuss these criterions, and whether they are appropriate for our application.
  • These four aesthetics for tree drawing, using a cartesian coordinate system, with root at (0, 0), growing downward, are as follows:
    1. Aesthetics 1: Nodes at the same depth (length of path from root to node) of a tree should have same y-coordinate. Thus nodes at depth d should be positioned with y-coordinate -d.
    2. Aesthetics 2: A left child should be positioned with the x-coordinate that is strictly less than the x-coordinate of its parent; similarly, a right child should be positioned with the x-coordinate that is strictly more than the x-coordinate of its parent.
    3. Aesthetics 3: A parent should be positioned with the x-coordinate (L+R)/2 over its left child and right child, whose x-coordinates are L and R respectively.
    4. Aesthetics 4: The drawing of a tree and its mirror image should be reflected to each other.
      1. The mirror image is a tree in which the left subtree is the mirror image of the right subtree of the original tree and the right subtree is the mirror image of the left subtree of the original tree.
      2. The mirror image of a trivial tree is also a trivial tree.
      3. Furthermore, the drawing of equal subtrees should be the same regardless of the position in the tree (i.e., there is one translation vector (given by the positions of the roots of the subtrees) such that translating the coordinates of the drawing of one subtree yields the coordinates of the other).
  • The main application is the direct investigation of search trees as created by the OKsolver and other backtracking solvers.
  • Labellings:
    1. Nodes are labelled with some symbolic information (like the branching variable), which can be shown by clicking on the node.
    2. Then there is numerical information on the nodes, which can be selected, and then shown for the whole tree, using some colour scheme.
    3. Also the edges can carry numerical information; one could try also to use here some colour schemes.
    4. See "Applications" in GraphDrawing/plans/general.hpp.
  • These tools should also be useful to investigate branching heuristics according to the theory by OK as handled in ComputerAlgebra/Satisfiability/Lisp/BranchingTuples/plans/general.hpp.

Definition in file Trees.hpp.