Directed Acyclic Graph with Hierarchical Layout

Question

I am trying to programmatically build a family tree. I don't care what format the input data is in, as text is easy to parse (I'm an NLP researcher), but I'm having trouble figuring out how to build (display) the tree. Here are my issues:

1. Family trees are not trees. A tree is a structure where each child node has one-and-only-one parent node. Family trees are actually directed acyclic graphs (DAGs).

2. There are many libraries out there that can generate DAGs, but those visualizations are not static, and they typically aren't pleasing to look at. Some examples:

   • Kingraph generally does what I want, but it fails to draw edges that don't look disconnected and unclean.
   • Descendent Tree looks amazing, but it is strictly a tree, not a DAG. I've played with turning it into a DAG, but I don't think it's possible.
   • Graphviz can do exactly what I'm looking for, except that I cannot get it to draw edges from the parent to the center of the child (see my previous question).

In summary, I need a framework to:

1. parse family tree data,
2. build a DAG from the data,
3. and generate an SVG of the DAG with a hierarchical layout so it visually looks like a tree.

I know I won't be able to find something that does all three (I've spent two weeks searching), but I'm hoping to find something that does the latter, or at least some help developing an algorithm to do so. At this point, I don't care if I need to learn a whole new language to be able to do this. I'm asking for a lot, but any resources, libraries, or suggestions you can send my way would be a huge help.

Disclaimer I am not looking for any of the following:

• a paid (or free) service, such as ancestry.com with built-in family tree visualizations,
• a manual approach to drawing nodes/edges, such as LucidChart or Family Echo

I am solely looking for the algorithm to do the hierarchical layout. Thanks!

Riocard

Did you find a solution? – Lingam

@WizardofKneup Nope. I played around with existing tools, but nothing generated the output I wanted, and I don't have time to learn the math for layouts and implement it. Any ideas? – Riocard

I use Graphviz for layouting as well. Did you already experiment with "headclip" and "headport" attributes? Otherwise, for my Vithanco.com software do I use Graphviz just as a library and draw the nodes and edges myself. I can fix quite some issues that way, e.g. Graphviz gets confused with edge direction sometimes. My software fixes that as it only uses the edge path. Happy to explain more. Maybe Vithanco should do your drawings :-) – Lingam

"directed acyclic graphs". Hopefully. – Hinkle

Answer 1

In case anyone comes across this and still needs a solution: Graphviz supports record-based and user- defined node shapes which give you complete control over how to render graphs. See: https://graphviz.org/doc/info/shapes.html#html

Equestrian

Answer 2

Why don't you use Dagre? It was built for this specific purpose

It implements a few CS papers from the '70s that heuristically render acyclic graphs. In fact, I used it to build the DAG component for Vertex AI here, which is now open-sourced: @google/workflow-graph

Terrazzo