Как я могу предотвратить дублирование в генераторе генеалогического древа?

Я собираюсь дать сложный ответ, потому что эта ситуация сложнее, чем вы думаете. Алгоритмы построения графиков - активная область исследований. Легко попытаться применить алгоритм, который проще простого, а затем он резко потерпит неудачу, если вы сделаете необоснованные и обычно скрытые предположения.

В общем, графы генетического наследования не плоские (см. Планарные графы на Википедия). Хотя это редкость, но, конечно, бывает, что все родовые отношения не связаны с уникальными людьми. Так бывает, например, когда у троюродных братьев есть дети.

Другая неплоская ситуация может возникнуть в ситуации детей от немоногамных родителей. Самый простой пример - двое мужчин и две женщины, у каждой пары с детьми (то есть как минимум четверо). Вы не можете выложить даже четыре родительские пары в один ряд без изогнутых линий.

Это только примеры. Я уверен, что вы откроете для себя больше, работая над своим алгоритмом. Настоящий урок здесь состоит в том, чтобы явным образом смоделировать класс отношений, который может определить ваш алгоритм, и иметь код проверки в алгоритме, чтобы определять, когда данные не соответствуют этим требованиям.

Однако вопрос, который вы на самом деле задаете, гораздо более простой. У вас возникают основные трудности, потому что вам нужно использовать обход в глубину график. Это (самый простой) полный вариант того, что значит выкладывать «сверху вниз» (в одном из комментариев). Это только один из многих алгоритмов обхода дерева.

Вы строите ориентированный граф с (по крайней мере) неявным понятием ранга. Субъект имеет ранг 0; родители - 1 ранг; дедушки и бабушки на 2-м месте. (Что касается предупреждений выше, ранжирование не всегда уникально.) Большая часть таких графов относится к родословной. Если вы не разместите сначала листовые узлы, у вас нет никакой надежды на успех. Идея состоит в том, что сначала вы размещаете узлы с наивысшим рангом, постепенно добавляя узлы с более низким рангом. Обход в глубину - наиболее распространенный способ сделать это.

Я бы рассматривал это как алгоритм перезаписи графа. Базовая структура данных представляет собой гибрид визуализированных подграфов и нижележащего графа предков. Отрендеренный подграф - это (1) поддерево всего графа с (1a) набором потомков, все предки которого визуализируются, и (2) набором данных визуализации: положения узлов и линий и т. Д. Начальное состояние гибрида представляет собой весь граф и не имеет отрисованных подграфов. Конечное состояние - это визуализированный весь граф. Каждый шаг алгоритма преобразует некоторый набор элементов на границе листа гибридного графа в (более крупный) визуализированный подграф, уменьшая количество элементов в гибриде. В конце есть только один элемент, граф рендеринга в целом.

Поскольку вы уже используете Family Echo, я бы посоветовал вам посмотреть, как они создают свою онлайн-диаграмму генеалогического древа. , поскольку они, кажется, решили вашу проблему.

Когда я ввожу ваш образец диаграммы в Family Echo, я могу построить красивое дерево, которое кажется именно тем, что вы ищете, без пересечения.

Хотя они создают свои диаграммы с помощью html и css, вы можете добавлять людей к их диаграммам один за другим, а затем проверять, где расположены блоки с точки зрения расположения левого и верхнего пикселей каждого элемента.

Если бы у меня было больше опыта в JavaScript, я бы попытался создать код, чтобы воспроизвести часть того, что делает Family Echo, но, боюсь, это не мое моджо.

вам нужно будет отрегулировать все ответвления от узла, на который вы воздействуете, каждая ветвь должна будет пересчитать положение своих узлов, и каждый узел придется пересчитывать локально, достигая листьев. чтобы пересчитать все время до резервного копирования, все это рекурсивно. Это похоже на настоящее дерево, когда вы физически добавляете ветвь к стволу ... другие ветки перемещаются самостоятельно, чтобы оставить место, все листы автоматически сбрасываются, так что вы должны представить. И смоделируйте этот процесс на своей диаграмме. Обрабатывает каждую ветвь до каждого листа и пересчитывает, чтобы пересчитать измененные соседи узла. (на один уровень выше, чем вы начали) Это непростая задача.