У меня есть база данных с информацией о многих гипотетических людях. Эти данные ориентированы на создание графа, связывающего связанных людей. Этот график должен представлять генеалогическое дерево в соответствующей структуре данных c ++. Все идет нормально. У меня есть структура данных, содержащая информацию о семье, где каждый человек является узлом, и все они связаны соответствующим образом в дереве.
Теперь проблема в том, что я потерялся в том, как генерировать визуальные данные для этого семейного графа. Для любого конкретного семейства мне нужно сгенерировать типичный граф, как вы могли бы увидеть в традиционном генеалогическом дереве. Я намерен визуализировать данные с помощью OpenGL и настроить все, чтобы это сделать. Моя единственная проблема заключается в том, как сгенерировать правильные позиции и размеры для прямоугольника каждого человека, чтобы в итоге не было совпадений, и каждое поколение людей находилось в одной вертикальной позиции. Затем я должен добавить традиционные линии, соединяющие каждый узел в визуальных данных, но это не должно быть большой проблемой.
Есть ли легковесные библиотеки, подготовленные для выполнения этой функции, или кто-то может помочь мне разработать алгоритм для решения этой проблемы? Спасибо
рекомендую В&T GraphVis библиотека. Эта библиотека используется Doxygen для построения диаграмм наследования и вызова деревьев.
Вы также можете искать «c ++ tree draw».
Еще один способ сформулировать проблему: как определить расположение узлов в иерархическом ориентированном графе, чтобы не было перекрытия, и узлы в одной иерархии размещались на одном уровне? (Здесь узлы соответствуют членам семьи, а поколение задает иерархию).
В то время как GraphVis может предоставить решение для макета, более новый подход, чем алгоритмы, используемые в GraphVis метод Dig-CoLa (ориентированный граф с помощью минимизации ограниченной энергии), описанный в Дуайер и соавт. 2005. Преимущество Dig-Cola состоит в том, что он также изящно обрабатывает определенные угловые случаи (например, циклы) и избегает введения иерархии, не вызванной исходными данными в таких случаях.
Основная идея этого метода состоит в том, чтобы сформулировать и решить проблему компоновки как ограниченную задачу оптимизации путем минимизации стресс (или энергия) функция основана на положениях узла под ограничения индуцируется иерархией информации.
Оригинальная бумага Dig-Cola для получения дополнительной информации:
Дуайер, Тим и Иегуда Корен. «Dig-CoLa: направленный макет графа за счет минимизации энергии с ограничениями». Симпозиум IEEE по визуализации информации, 2005. INFOVIS 2005 .. IEEE, 2005.
(Полный текст в настоящее время доступен Вот)
Автор также предоставляет несколько примеров и код для этого метода (и более поздних расширений) Вот.