LINUX.ORG.RU
Форум — Development  

Раскидать элементы графа по сетке

 ,


0

1

Есть дерево (без циклов). Выглядит примерно так: https://s32.postimg.org/mb44h9anp/before.png . Мне нужно раскидать элементы по сетке (можно считать бесконечной), располагая детей под родителями (нечетное кол-во - сразу под, четное - с пропуском по середине). Т.е. хочу сделать вот так: https://s32.postimg.org/8eew8nx5x/after.png .

Подскажите, пожалуйста, алгоритм действий.

Ответ на: комментарий от someoneelsenotme

А есть какая-то проблема? Начинаешь с корня, на каждом уровне распределяешь детей по колонкам относительно родителя как тебе нужно (я не совсем понял как распределить, например, 4 ребёнка. с дыркой посередине?). Как только случилось столкновение, определяешь сколько ячеек тебе не хватает и двигаешь на этот размер текущий уровень, потом идешь вверх к корню и выравниваешь родителей.

slovazap ★★★★★
()
Ответ на: комментарий от slovazap

как распределить, например, 4 ребёнка. с дыркой посередине?

Да

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

Хм... так еще не пробовал. Начинал с детей. Сейчас попробую с корня.

someoneelsenotme ★
() автор топика
Ответ на: комментарий от someoneelsenotme

Изучай :)

https://cs.brown.edu/~rt/gdhandbook/chapters/trees.pdf
https://cs.brown.edu/~rt/gdhandbook/chapters/hierarchical.pdf

А тут есть простенький код на си, если конечно найдешь еще эту работу в свободном доступе (пару лет назад - была):
A. Bloesch. “Aesthetic Layout of Generalized Trees”. Software - Practice and Experiance, vol. 23(8), 817–827, aug 1993.

invy ★★★★★
()
Последнее исправление: invy (всего исправлений: 1)
Ответ на: комментарий от slovazap

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

someoneelsenotme ★
() автор топика
Ответ на: комментарий от invy

Изучил. Тут не рассматривается мой ограниченный случай с со строгой сеткой. А без нее у меня и так есть структура в памяти которую можно отобразить с каким-нибудь резиновым интерфейсом типа html.

someoneelsenotme ★
() автор топика

Решил попробовать, что там не получается. Набыдлокодил вот. Там скорее всего можно упростить и точно можно написать лучше, но общая идея должна быть ясна. Проход один, сверху-вниз и слева-направо. Поддерживается левая граница/фронт и по ней при необходимости выполняется корректировка координаты X. При некоторых конфигурациях оно выглядит странно, но это скорее из-за ascii-арта, а в целом должно как-то так работать.

xaizek ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development