я дуже горжуся як я це абстрагував. просто в клас прокидаються функції, які роблять кроки по графу, але саме обрахування координат міститься тільки в середині імплементації класу: https://github.com/TheBestTvarynka/grafily/blob/feat/direct-ancestors-descendants-tree/src/layout/tree.ts#L69-L88

class ReingoldTilford {
    getRightmostChildren: (id: Id, family: Index) => Id | null;
    getLeftmostChildren: (id: Id, family: Index) => Id | null;
    getChildNodesIds: (currentNode: Id, family: Index) => Id[];
    getY: (level: number) => number;
    family: Index;

    constructor(
        getRightmostChildren: (id: Id, family: Index) => Id | null,
        getLeftmostChildren: (id: Id, family: Index) => Id | null,
        getChildNodesIds: (currentNode: Id, family: Index) => Id[],
        getY: (level: number) => number,
        family: Index,
    ) {
        this.getRightmostChildren = getRightmostChildren;
        this.getLeftmostChildren = getLeftmostChildren;
        this.getChildNodesIds = getChildNodesIds;
        this.getY = getY;
        this.family = family;
    }

// ...

ось так виглядає зараз. я добавив людей та об'єднав дерева батьків та дітей.

навіть дітей можна колапсити (ви бачите кнопки мінус на вузлах)

стрілочкою вказана starting node

гляньте що я випадково знайшов: https://github.com/NorthwoodsSoftware/GoJS

по-ідеї, воно імплементує один із алгоритмів, що мені треба

https://gojs.net/latest/samples/ldLayout.html

у них ще є класна демка. треба у себе локально запустити та спробувати внести дані родинного дерева. якщо леяут буде нормальний, тоді варто імплементовувати цей алгоритм

дуже потужна ліба. тут приклади використання: https://gojs.net/latest/samples/

як добре що є ai.
клонував репу. тикнув у потрібний sample і сказав написати такий самий, але координати графа захардкодити замість автогенерування.

в принципі, алгоритм працює добре.
там є багато дрібних косяків. дещо не по центру. дещо треба було свапати місцями щоб було норм.

проте свапання можна легко пофіксити власною імплементацією обходу графа. головне що overall layout виглядає нормально та видно зв'язки

ось так воно мало виглядати

my next goal: намалювати такий граф

Погані новини: вчора не додивився що сама бібліотека closed source. Не вийде подивитися як працює їхній алгоритм під капотом. Ну і фіг ними.

Хороші новини: Я знайшов інші імплементації з відкритим кодом

https://erikbrinkman.github.io/d3-dag/
https://github.com/erikbrinkman/d3-dag

працєю за алгоритмами Sugiyama framework. те, що мені треба.

https://github.com/dagrejs/dagre

згідно їх доки (https://github.com/dagrejs/dagre/wiki#recommended-reading), вони не використовують оригінальний Sugiyama framework. проте спирають на подібні алгоритми. найголовніше, що вони використовують Brandes and Köpf алгоритм для визначення координат. із усього Sugiyama framework, Brandes and Köpf це те, що для мене актуально

For positioning (or coordinate assignment), we derived our algorithm from Brandes and Köpf, "Fast and Simple Horizontal Coordinate Assignment". We made some adjustments to get tighter graphs when node and edges sizes vary greatly.

також ця ліба інтегрується легко у reactflow (інша ліба, яку я використовую для рендера)

https://js.cytoscape.org/

Graph theory (network) library for visualisation and analysis

чим більше риюся тим більше знаходжу ліб для рендера графів. треш скільки їх є