Width of Trees (from Yahoo group)

fablhx commented 7 years ago

From @GuillaumeBrochu on August 29, 2016 13:46

(published on the Yahoo group on 28-08-2016, https://groups.yahoo.com/neo/groups/geneweb/conversations/messages/6736)

Hi,

This message is addressed to the coders and maintainers of GeneWeb.

I love the system and have been using for many years both on Geneanet and on my own "Vaucher" databases housed at U.deMontreal. I especially like the ANCESTOR and DESCENDANT tree facilities except for one thing... the excessive width of the printed trees. I ran across this when I added about 200 new Vauchers from Uruguay and Brazil to my database and similarly with my French Canadian family with 12-15 children per generation.

Geneweb uses a simple grid layout scheme which uses one "column" for every LEAF - a couple without children - (See attached JPG): (N/2) columns in the BEST case for N people; but often close to N columns. However simple algorithms exist which give much slimmer yet elegant trees. Many papers were published on the subject around 1980 . I published one in "Software Practice and Experience" vol 10, 553-561 (1980) but independently Wetherell published in IEEE Trans of Software engineering (sept 1979) and Reinhold in IEEE Trans Soft Eng (March 1981).

Example: Assume X has 3 generations of descendants in which there is only one fruitful child per generation, like below. It is fairly clear that you could print the children of every generation right under the previous one, using only 5 columns for the 16 people.


                    X

                    |

              +--+--+--+--+

             12 13 14 15 16

                    |

              +--+--+--+--+

              6  7  8  9  10

                    |

              +--+--+--+--+       

              1  2  3  4  5

However, Geneweb will use the following layout with 12 columns (over twice the size):

                    X

                    |

   +--+-------------+---------------+--+

   12 13            14              15 16

                    |

        +--+--------+--------+--+

        6  7        8        9  10

                    |

              +--+--+--+--+       

              1  2  3  4  5

If anyone is interested, I will send the pseudo code or copies of the articles. I repeat, "the algorithm is TRIVIAL"

Jean Vaucher

jgvaucher@...

_Copied from original issue: geneweb/genewebtmp#60

fablhx commented 7 years ago

From @vaucher on September 10, 2016 4:28

I include a zipped folder with a complete Java program which produces trees which are much narrower than the ones presently produced by Geneweb. The KEY part of the program is a small "position"; algorithm which determines X,Y positions for each Node.

The program itself is much larger because it includes INPUT routines to read tree descriptions and HTML OUTPUT routines. The HTML produced is quite primitive compared to Geneweb's but sufficient to show what "POSITION"; can do. Tree_export.zip

GuillaumeBrochu commented 7 years ago

Tree_export_Jean_Vaucher_2016_09_09.zip

a2line commented 7 years ago

Article original :

Jean Vaucher, ''Pretty-Printing of Trees'', 1980 (.docx, en images sur dropbox).

a2line commented 7 years ago

From @vaucher on October 6, 2016 : « Je ne prétend pas pouvoir améliorer les arbres (ou graphes) quelconques; mais je note qu'une idée simple publiée en 1980 peut générer des arbres classiques (ascendants ou descendants) plus étroits que ceux présentement imprimés. Je ne connais pas assez OCaml pour modifier Geneweb; mais pour faciliter le travail des implanteurs éventuels, j'inclus une version modifiée du programme Java que j'avais expédié il y a quelques temps. J'y ai rajouté ma version du code de Geneweb . Le programme lit une description simple d'un arbre et génère une page HTML avec un arbre version GENEWEB et un autre version Compact. Une variable dans le programme permet de colorier les cellules afin de mieux voir la structure HTML. Comme avec Geneweb, les parents ont droit à des cellules triples. »

figure_2060 figure_2061

Tree_export_Jean_Vaucher_2016_10_06.zip (merci @GuillaumeBrochu pour l'ul!)

Swrup commented 2 years ago

Vaucher tree added in #1335

a2line commented 2 years ago

Merci pour ce « pont ». Pour l'histoire, Henri Gouraud (@hgouraud) a réussi récemment à coder l'algorithme de réduction de graphe descendant de Jean Vaucher dans GeneWeb. Il est possible que l’on puisse en profiter dans la version 7.1 à venir ! Le résultat n’est pas pertinent pour tous les graphes ie. la réduction en largeur n’est pas toujours notable, mais elle l’est dans certains cas et c’est appréciable bien que parfois perturbant sur la forme car le rendu est nouveau (question d'habitudes). Un nouveau menu avancé a été ajouté en haut des arbres pour y accéder et naviguer entre les options sur les arbres.

Une autre option liée remplit partiellement une requête de mwhite (#381) et permet d'élaguer un long arbre descendant en largeur en ne gardant que le fil conducteur entre l'ancêtre et sa racine. La requête initiale d'élaguer les branches « mortes avant la génération choisie » reste à implémenter.

vaucher commented 2 years ago

Merci les gars ! J'ai hate de voir ce que ca donne.

a2line commented 1 year ago

Ça devrait être dans le master avec le merge de la PR template #1396. À peaufiner surement encore un peu.

geneweb / geneweb

Width of Trees (from Yahoo group) #414