View source for Narrated Website Ancestry Tree Design Notes

The source code that generates the Ancestry Tree portion of the Narrated Website can be found below [https://github.com/gramps-project/gramps/tree/master/gramps/plugins/webreport Gramps/gramps/plugins/webreport] in a Gramps source code tree.

The Narrated Website Report can include an Ancestry Tree.  The layout of the tree uses a tree generating algorithm created by [[#walker|Walker]] and then improved by [[#buchheim|Buchheim]] et.al.

The tree is first defined as a series of objects each containing a node plus references to the child-nodes of this node and the Buchheim algorithm then uses these child/parent relationships, together with a minimum separation vertically and horizontally, to determine a reasonable layout.  The generated tree provides an X and Y coordinate for each node.

Within the Gramps Narrated Website Report, the following objects and relationships are generated:

* Each node (person) is represented by a LayoutTree object which references 'children' objects and stores the handle for a Gramps Person object
* For the Ancestry tree, a 'child' of a node is actually a parent (so we expect there to be only 0/1/2 parents but the algorithm would allow more)
* The top-mode node, the root of the tree, is provided to the Buchheim algorithm which returns a DrawTree object defining the layout.

Each DrawTree node contains X and Y coordinates and references a LayoutTree node and therefore a Person.

The Ancestry tree is a series on interconnected boxes so the remainder of the process is drawing the tree based on the DrawTree information.  The following gives an overview of the process and references some internal variables in the code.

* The tree is drawn within an HTML element which defines a space on the page large enough for the tree.
* The tree is drawn _XOFFSET pixels to the right and _YOFFSET down from the top to provide a nice border; similar space is allowed for when defining the containing HTML element.
* The node is draw 'as big as required' up to a maximum depth of _HEIGHT; this can leave some larger vertical gaps between nodes where information about the person is sparse so a small box can contain everything.
* Related node boxes are separated by at least _HGAP horizontally and _VGAP vertically but this gaps can be bigger depending no the layout requirements of other nodes.
* Connecting lines are drawn between the child to parent(s) but this is done in two stages:
** If this child has parents, a line is drawn form the child horizontally towards the parent (stopping at the midpoint between them)
** Each parent draws a horizontal line back towards the child and a vertical line to join the parent and child's horizontal lines
* Connecting lines meet a person box _LOFFSET from the top of the box (and not relative to the bottom).  This allows boxes to be be of variable depth without lines either being left floating of the box doesn't reach down to them or requiring complex calculations to determine an offset relative to the bottom of the box.

The actual Walker and Buchheim algorithms are well documented in the referenced papers and the actual HTML drawing is best understood by reading the code.

Finally it is noted that although the algorithm draw from left to right, it can easily be modified to draw from right to left, top to bottom or bottom to top.

The algorithm might also be useful for other parts of Gramps such as the Graphical Reports Ancestor or Descendents Tree.

==References==
* <span id="walker">J. Q. Walker II</span>. [http://www.cs.unc.edu/techreports/89-034.pdf A node-positioning algorithm for general trees]]. ''Softw. – Pract. Exp.'', 20(7):685–705, 1990.
* <span id="buchheim">C. Buchheim</span>, M. Jünger, and S. Leipert. [http://dirk.jivas.de/papers/buchheim02improving.pdf Improving Walker’s algorithm to run in linear time]. In Michael T. Goodrich and Stephen G. Kobourov, editors, ''Graph Drawing (Proceedings of 10<sup>th</sup> International Symposium on Graph Drawing, 2002)'', volume 2528 of ''Lecture Notes in Computer Science'', pages 344–353. Springer, 2002.
* Roberto Tamassia, Editor. [https://cs.brown.edu/people/rtamassi/gdhandbook/chapters/trees.pdf Chapter5 : Tree Drawing Algorithms] in ''[https://cs.brown.edu/people/rtamassi/gdhandbook/ Handbook of Graph Drawing and Visualization]''. CRC Press, 2013.
* [https://github.com/gramps-project/gramps/pull/548 Add Buchheim tree ancestor trees to Narrated Web Report #548]
* [http://gramps.1791082.n4.nabble.com/Where-should-I-put-design-notes-td4681555.html Where should I put design notes? ]

==See also==
* [[Gramps_{{man version}}_Wiki_Manual_-_Reports_-_part_7#Html_options]]  - [x] Include ancestor's tree

[[Category:Developers/Reference]]
[[Category:Proposed_Report_Specifications]]
[[Category:GEPS]]