Алгоритм отрисовки: Как программно найти «супружеский ID» (spouseId) для конкретного узла в генеалогическом древе, учитывая связи типа «многие ко многим» в графе?
В генеалогическом дереве каждый узел представляет человека, а рёбра — семейные отношения. Сложность возникает, когда один человек может состоять в нескольких браках (повторные браки, исторические полигамные союзы), то есть граф содержит связи типа «многие ко многим» между узлами-персонами.
## Структура данных
Для корректной работы алгоритма рекомендуется хранить не прямые ссылки person → spouse, а промежуточные узлы-семьи (Family Node):
Person { id, name, familyIds[] }
Family { id, spouseAId, spouseBId, childrenIds[] }
Такой подход позволяет одному человеку участвовать в нескольких семьях без дублирования данных.
## Алгоритм поиска spouseId
1. **Получить список семей узла.** По `personId` найти все записи `Family`, где `spouseAId === personId` или `spouseBId === personId`.
2. **Извлечь супруга из каждой семьи.** Для каждой найденной семьи:
— Если `family.spouseAId === personId`, то `spouseId = family.spouseBId`
— Иначе `spouseId = family.spouseAId`
3. **Вернуть массив супругов.** Так как связи «многие ко многим», результатом будет `spouseIds[]`, а не единственный ID.
javascript
function getSpouseIds(personId, families) {
return families
.filter(f => f.spouseAId === personId || f.spouseBId === personId)
.map(f => f.spouseAId === personId ? f.spouseBId : f.spouseAId)
.filter(id => id !== null); // учитываем одиноких родителей
}
## Обработка граничных случаев
— **Одинокий родитель:** одно из полей `spouseAId` или `spouseBId` может быть `null`. Алгоритм должен это обрабатывать.
— **Самосвязь:** проверяйте, что `spouseAId !== spouseBId`.
— **Циклы в графе:** при обходе всего дерева используйте множество `visited` для предотвращения бесконечных циклов.
— **Хронология браков:** добавьте поля `startDate` и `endDate` в узел `Family` для сортировки супругов по времени.
## Алгоритм для отрисовки
При визуализации генеалогического дерева супруги обычно размещаются горизонтально рядом с узлом. Для каждого узла:
1. Вызвать `getSpouseIds(nodeId, families)`.
2. Для каждого `spouseId` создать горизонтальное ребро «супружество».
3. Вертикальные рёбра вести от узла `Family` к детям.
Такой подход разделяет логику отношений и визуализацию, упрощая поддержку сложных случаев.
## Оптимизация
Для больших деревьев (тысячи узлов) рекомендуется построить индекс: `Map` — это снизит сложность поиска с O(n) до O(1) на запрос.